You are given intervals, a list of ranges [start, end] with start ≤ end. Two ranges overlap
if they share at least one point, so [1, 3] and [3, 5] overlap.
Merge every group of overlapping ranges into a single range covering all of them, and return the merged ranges sorted by start.
Example 1
- Input
- intervals = [[1, 4], [8, 10], [2, 6], [15, 18]]
- Output
- [[1, 6], [8, 10], [15, 18]]
[1, 4] and [2, 6] overlap, so they become [1, 6].Example 2
- Input
- intervals = [[1, 3], [3, 5]]
- Output
- [[1, 5]]
Constraints
intervalsholds 1 to 10⁴ ranges.- 0 ≤
start≤end≤ 10⁴
Show the pattern
Intervals
Once intervals are sorted by start, any overlap is with the interval just before, so one pass that extends or closes the current interval merges everything.
See intervals in a visualiserShow the approach
Sort the ranges by start. Keep a list of merged ranges, starting with the first. For each next range, if its start is at most the last merged range's end, they overlap: stretch that end to the larger of the two ends. Otherwise the range begins a new merged range.
Time: O(n log n) · Space: O(n) for the output