Merge Overlapping Intervals
You get a list intervals. Each item is a pair [start, end] with start <= end. The list is not sorted.
Merge every group of intervals that overlap into one interval that covers all of them. Keep doing this until no two intervals in the list overlap.
Return the merged list, sorted by start.
Note
- Two intervals that only touch at an end point, such as
[2, 5]and[5, 8], count as overlapping. Merge them into[2, 8]. - An interval may have
start == end. It is a single point. - Return a new list of pairs.
Hint: after you sort the intervals by start, an interval can only merge with the last interval you have already built.
Examples
Example 1
- Input:
- [[8,12],[1,3],[2,6],[15,18],[10,11]]
- Output:
- [[1,6],[8,12],[15,18]]
[1, 3] and [2, 6] overlap, so they become [1, 6]. [10, 11] is inside [8, 12], so they become [8, 12]. [15, 18] overlaps nothing.
Example 2
- Input:
- [[5,7],[0,5]]
- Output:
- [[0,7]]
[0, 5] ends at 5 and [5, 7] starts at 5. They touch, and touching counts as overlapping, so the answer is one interval [0, 7].
Example 3
- Input:
- [[9,9],[3,4],[6,7]]
- Output:
- [[3,4],[6,7],[9,9]]
No two intervals overlap or touch. The answer is the same three intervals, sorted by start.
Constraints
1 <= intervals.length <= 150 <= start <= end <= 100
Run checks your code against the 3 examples. Submit checks it against all 183 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.