Merge Intervals
01 / The one-sentence essence
Sort intervals by start, then sweep left to right — each interval either extends the current merge or commits it and starts a fresh one. The whole pattern lives in that one comparison.
Problemmerge all overlapping intervalsInput[1,3] [2,6] [8,10] [15,18]
Input has 4 intervals. The bars below are drawn in their original order.
step
0 / 12
current
—
result
0
0 / 12
02 / The pattern signature
# sort by start, then sweepintervals.sort(key=start)result ← []for [s, e] in intervals:if result is empty or result.last.end < s:result.push([s, e]) # commit newelse:result.last.end ← max(result.last.end, e) # extend# overlap test: result.last.end ≥ s (after sorting by start)
03 / When to recognize this pattern
"merge overlapping intervals"
The literal canonical signal. The output count is at most the input count, often less. If the count stays the same, the pattern shrinks to a sanity check.
"meeting / booking / schedule"
Calendar-shaped problems: rooms, flights, employee free time. The intervals carry an implicit timeline.
"insert into sorted intervals"
A variant where the existing list is already sorted and you add one interval — the merge logic is the same, you just sweep until the new interval finds its place.
"remove minimum to make non-overlapping"
Greedy variant — sort by end instead of start, then count how many overlap and must be dropped. Different sort key, same sweep skeleton.
04 / Common pitfalls
i.
Sorting by the wrong key.
For merging, sort by
start. For greedy "keep as many non-overlapping as possible", sort by end. They are not interchangeable — sort by end and the merge loop above misses overlaps that span across earlier intervals.ii.
Strict vs non-strict overlap.
Does
[1, 3] meeting [3, 5] count as overlapping? Read the problem twice. The merge test is result.last.end ≥ s when touching counts, result.last.end > s when it doesn't. Mixing them up flips the answer.iii.
Mutating the input in place when you shouldn't.
The pattern naturally reads as an in-place sweep: pop, compare, merge into the previous, push. Convenient — but if the caller still owns
intervals afterwards, you've quietly destroyed their data. Copy first.05 / Go practice — on LeetCode
Four problems, ordered by difficulty. No solutions here, by design.