LeetCode 56 · Intervals · concept: overlapping-intervals
Problem
Merge all overlapping intervals.
[[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]
Approach — sort by start, then sweep (optimal)
Sort by start time so overlapping intervals become adjacent. Walk through; if the current interval starts at or before the last merged interval’s end, they overlap — extend the last one’s end. Otherwise start a new interval.
def merge(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps the last merged interval
merged[-1][1] = max(merged[-1][1], end) # extend its end
else:
merged.append([start, end]) # disjoint -> new interval
return mergedTime O(n log n) (the sort dominates), space O(n).
Why sorting by start is the enabler
After sorting by start, any interval that overlaps an earlier one must overlap the most recent merged interval (all earlier ones start no later). So a single “does this overlap the last?” check per interval is enough — no need to compare against all previous. This “sort, then one linear merge pass” is the interval template.
Key insight
Interval merging → sort by start, then extend-or-append in one pass. Almost every interval problem opens with this sort; overlapping candidates become neighbors, collapsing an O(n²) all-pairs comparison to O(n log n).
Related
- concept: overlapping-intervals, sorting
- prev: Insert Interval · next: Non-overlapping Intervals
Software engineering
Infrastructure & security
Computer science
Hardware & engineering