Merge Intervals
Given a collection of closed intervals, merge every group of overlapping intervals and return the resulting non-overlapping intervals that cover the same points.
- 1 ≤ intervals.length ≤ 10^4
- 0 ≤ start ≤ end ≤ 10^4
- Intervals with overlap
- After sorting by start, an overlap can only be with the last merged interval
- Single linear pass after sorting
Sort by start (or end) time and sweep: two intervals overlap iff the next start is before the current end, and after sorting each interval only needs comparing with the one being built. Counting concurrent intervals is a sweep over sorted endpoints, or a min-heap of end times.
Sort by start. Walk through the intervals keeping the last interval of the output. If the current start is ≤ the last end, extend the last end to the max of the two ends; otherwise append the current interval as a new entry. Sorting guarantees that any interval overlapping an earlier one overlaps the most recently merged block.
- Without sorting you would need repeated O(n^2) pair merging. An interval tree supports dynamic insertions with merge queries.