Med.sortingintervals
Merge Intervals
Collapse a list of intervals so no two of them overlap.
Each entry of intervals is a pair [start, end] with start <= end. Merge every pair that overlaps or touches, and return the result sorted by start.
Two intervals touch when one ends exactly where the next begins: [1, 4] and [4, 5] merge into [1, 5].
Constraints
- 1 ≤ intervals.length ≤ 10,000
- -10⁹ ≤ start ≤ end ≤ 10⁹
- The input is not sorted
Examples
- Input
- intervals = [[1,3],[2,6],[8,10],[15,18]]
- Output
- [[1,6],[8,10],[15,18]]
- Why
- [1,3] and [2,6] overlap.
- Input
- intervals = [[1,4],[4,5]]
- Output
- [[1,5]]
- Why
- Touching counts as overlapping.
- Input
- intervals = [[5,7],[1,2]]
- Output
- [[1,2],[5,7]]
- Why
- Unsorted input, no overlap.
Submitting also runs 7 hidden tests.
Limits
2000 ms and 256 MB per test case.