Merge Intervals
Given an array of `intervals` where `intervals[i] = [start_i, end_i]`, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input. **Core Insight:** Sort the intervals by their start time. Then scan left to right: if the current interval overlaps the last merged interval (i.e. `current.start <= last.end`), extend the last interval's end to `max(last.end, current.end)`. Otherwise, the current interval is disjoint — push it as a new merged interval. **Algorithm:** Sort by start. Initialize result with the first interval. For each subsequent interval: if `interval.start <= result.last.end`, update `result.last.end = max(result.last.end, interval.end)`. Else append `interval` to result. **Why sorting helps:** After sorting, any overlapping intervals are guaranteed to be adjacent, so a single left-to-right pass is sufficient. **Complexity:** Time O(n log n) — dominated by sorting. Space O(n) — the output array.
Constraints
- •
1 ≤ intervals.length ≤ 10⁴
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged