The problem
Given a list of intervals, merge every group that overlaps (touching counts: [1, 4] and [4, 5] merge) and return the resulting intervals.
Examples
01
- Input
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
- Output
[[1, 6], [8, 10], [15, 18]]
02
- Input
intervals = [[1, 4], [4, 5]]
- Output
[[1, 5]]
03
- Input
intervals = [[4, 7], [1, 4]]
- Output
[[1, 7]]
Constraints
- 1 ≤ intervals.length ≤ 10⁴
- 0 ≤ start ≤ end ≤ 10⁴
The idea
Sort by start. Now an interval can only overlap the merged one just before it: everything earlier ended before that one began, or it would have been merged into it.
Walk the sorted list. If an interval starts no later than the last merged one ends, stretch that one’s end; otherwise it begins a new merged interval.
- Time
- O(n log n) — the sort
- Space
- O(n)
Solution · every language run against every case
class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort() # by start: overlapping intervals are now next to each other out = [] for s, e in intervals: if out and s <= out[-1][1]: out[-1][1] = max(out[-1][1], e) # overlaps the last one: stretch it else: out.append([s, e]) return out