Merge Intervals
Merge Intervals is a medium Intervals problem from the Blind 75. The key pattern is sort + sweep, and a good solution runs in O(n log n) time.
Problem
Merge all overlapping closed intervals and return them sorted by start.
Examples
Example 1
Input
[[1,4],[3,6],[8,10],[10,12]]Output
[[1,6],[8,12]]Example 2
Input
[[2,5],[4,8],[10,11],[11,15]]Output
[[2,8],[10,15]]Example 3
Input
[[3,6],[0,6]]Output
[[0,6]]Approach
Sort by start and merge each interval into the last kept one when it starts before that one ends.
| Pattern | Sort + sweep |
|---|---|
| Time | O(n log n) |
| Space | O(n) |
Watch out for
When merging, keep the larger of the two end values.