Merging Ranges
Given an array of intervals where each interval is a pair of integers representing a start and an end time, write a function that merges all overlapping intervals. The function should return the merged intervals in ascending order.
[ [ 1, 3 ], [ 2, 6 ], [ 8, 10 ], [ 15, 18 ] ]
[ [ 1, 6 ], [ 8, 10 ], [ 15, 18 ] ]
Explanation. Intervals [1, 3] and [2, 6] are overlapping and should be merged into [1, 6]. The others do not overlap.
[ [ 1, 4 ], [ 4, 5 ] ]
[ [ 1, 5 ] ]
Explanation. Intervals [1, 4] and [4, 5] are touching and should be merged into [1, 5].
[ [ 6, 8 ], [ 1, 9 ], [ 2, 4 ], [ 4, 7 ] ]
[ [ 1, 9 ] ]
Explanation. All intervals overlap with each other in some way and can be merged into a single interval [1, 9].
Follow-up: Can you improve your algorithm to operate in `O(n log n)` time complexity?
- Each pair in the array will represent an interval with a start time and an end time. - The start time will always be less than or equal to the end time. - Intervals are represented as arrays with two integer elements: `[start, end]`.
- Views
- 12