Menu
We are given a continuous stream of integer ranges like [1,3], [5,10], [2,6], ... when each new range comes, we need to check with existing ranges and see if it overlaps with any existing range, and if any overlap is found, all the overlapping ranges are removed and the merged range is inserted instead. We need an efficient algorithm for this. Note that the range comes one at a time which forms a stream...
Was asked this question during an interview. Ideas?
The intent is to merge overlapping ranges into one. for example, if we have 3 ranges coming in the following order: [1,3], [2,6], [5,10]. Then we first merge the first two into [1,6], then merge with the 3rd and it becomes [1,10].
836
A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from the list and merge the other into the first interval. Repeat the same steps for the remaining intervals after the first.
1) Sort all intervals in increasing order of start time. This step takes O(nLogn) time. 2) In the sorted array, if start time of an interval is less than end of previous interval, then there is an overlap.
The standard algorithm for this problem is an interval tree.
198
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
