Combine the ranges that overlap
MediumStuck?
Show a hintHide the hint
Sort by start. Walk once, extending the current interval while the next one starts at or before its end, taking the larger of the two ends.
The ideas behind this problem
Next in this lesson
How many must you dropGiven a list of intervals, combine every set that overlaps and return the result, sorted by where each one starts.
Two intervals overlap if they share any point, so [1,3] and [3,5] do overlap: they share the point 3.
Worked example#
For [1,3] [2,6] [8,10] [15,18], sort by start (already sorted here) and walk once:
| interval | overlaps the one being built? | result so far |
|---|---|---|
| [1,3] | nothing yet | [1,3] |
| [2,6] | 2 is not after 3, so yes | [1,6] |
| [8,10] | 8 is after 6, so no | [1,6] [8,10] |
| [15,18] | 15 is after 10, so no | [1,6] [8,10] [15,18] |
The answer is [1,6] [8,10] [15,18].
Why sorting by start is what makes this one pass#
Once sorted by start, anything that overlaps the interval you are building must come next. It cannot be further along, because every later interval starts even later. So a single pass sees every overlap, with no need to look back.
Without sorting you would have to compare every interval with every other, which is quadratic.
The mistake worth avoiding#
When you merge, compare the next interval against the merged end, not the original one.
Take [1,10] [2,3] [4,12]. After merging the first two the range is still [1,10]. Now [4,12] starts at 4, which is before 10, so it merges and the end becomes 12. Compare against [2,3]'s end of 3 instead and you would wrongly start a new interval.
So the merged end is max(current end, next end), not simply the next end. An interval completely inside another must not shrink it.
The cost#
Time O(n log n), dominated by the sort. Memory O(n) for the answer.
Constraints#
1 <= number of intervals <= 100000 <= start <= end <= 1000000
Input
intervals is a row count, then 2, then that many start and end pairs.
Output
The merged intervals, one per line, start then end.
Examples
Input
4 2 1 3 2 6 8 10 15 18
Output
1 6 8 10 15 18
The first two overlap and become 1 to 6. The rest stand alone.
Input
2 2 1 4 4 5
Output
1 5
They share the single point 4, which counts as overlapping.
Input
3 2 1 10 2 3 4 12
Output
1 12
The second sits inside the first and must not shrink it, then the third extends it.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.