Merge Intervals

Primer

An interval is just a start and an end on a number line. Sort by start, and one property carries every pass. Only the last interval you kept can still overlap the next one.

Do two intervals overlap?

startendtall line = later start, earlier end

Partial overlap

overlap

One inside the other

overlap

Touching at one point

overlap

half-open would say no

No overlap

no overlap

Green before red, overlap ahead. Red before green, gap in between.

The most basic skill is telling whether two intervals overlap at all. Find the later of the two starts and the earlier of the two ends. If that start comes at or before that end, they share a point, which in code is max(starts) <= min(ends). The figure shows those two lines on four shapes, and the rhyme to keep is Green before red, overlap ahead. Red before green, gap in between.

Variant	How it moves	Typical use
Sort by start, one pass	Carry a running end	Detect, merge, insert
Walk two sorted lists	Two cursors, in step	Set subtraction
Sort by end, one pass	Keep the earliest finisher	Most non-overlapping

The sort is the precondition, and an unsorted pass is wrong, not slow. Settle the convention before you write anything, too. Closed intervals [1, 4] and [4, 5] overlap at the shared point, while half-open [1, 4) and [4, 5) do not, and the whole difference is one character, <= against <. To keep the most intervals, sort by end so the earliest finisher leaves the most room. Counting intervals over a point belongs to line-sweep.

Approach	Time	Extra space
Compare every pair	$O(n^2)$	$O(1)$
Sort, then one pass	$O(n \log n)$	$O(n)$
Insert into already-sorted	$O(n)$	$O(n)$

It fits when a problem asks whether ranges collide, what they cover once merged, what remains after subtracting one set from another, or how many fit without overlapping.

The problems below start with detecting, merging, and inserting in One Sorted List, move through half-open subtraction across Two Sorted Lists, and end with Sorting by End to keep the most non-overlapping.

Primer

An interval is just a start and an end on a number line. Sort by start, and one property carries every pass. Only the last interval you kept can still overlap the next one.

Do two intervals overlap?

startendtall line = later start, earlier end

Partial overlap

overlap

One inside the other

overlap

Touching at one point

overlap

half-open would say no

No overlap

no overlap

Green before red, overlap ahead. Red before green, gap in between.

Variant	How it moves	Typical use
Sort by start, one pass	Carry a running end	Detect, merge, insert
Walk two sorted lists	Two cursors, in step	Set subtraction
Sort by end, one pass	Keep the earliest finisher	Most non-overlapping

Approach	Time	Extra space
Compare every pair	$O(n^2)$	$O(1)$
Sort, then one pass	$O(n \log n)$	$O(n)$
Insert into already-sorted	$O(n)$	$O(n)$

It fits when a problem asks whether ranges collide, what they cover once merged, what remains after subtracting one set from another, or how many fit without overlapping.

Merge Intervals

Primer

Problems5

One Sorted List

Two Sorted Lists

Sorting by End

Merge Intervals

Primer

Problems5

One Sorted List

Two Sorted Lists

Sorting by End