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[1,3][2,6][8,10][15,18]result
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

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.
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.
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

easy1

01Meeting Rooms— LC 252→

medium16

01Merge Intervals— LC 56→02Insert Interval— LC 57→03Meeting Rooms II— LC 253→04Non-overlapping Intervals— LC 435→05Minimum Number of Arrows to Burst Balloons— LC 452→06Add Bold Tag in String— LC 616→07Maximum Length of Pair Chain— LC 646→08My Calendar II— LC 731→09Partition Labels— LC 763→10Interval List Intersections— LC 986→11Video Stitching— LC 1024→12Car Pooling— LC 1094→13Remove Interval— LC 1272→14Remove Covered Intervals— LC 1288→15Divide Intervals Into Minimum Number of Groups— LC 2406→16Count Ways to Group Overlapping Ranges— LC 2580→

hard9

01The Skyline Problem— LC 218→02Data Stream as Disjoint Intervals— LC 352→03Range Module— LC 715→04My Calendar III— LC 732→05Employee Free Time— LC 759→06Rectangle Area II— LC 850→07Maximum Profit in Job Scheduling— LC 1235→08Minimum Number of Taps to Open to Water a Garden— LC 1326→09Minimum Interval to Include Each Query— LC 1851→