4.27.0 — Intervals: The Pattern

Recognition cue. The input is pairs of (start, end) — meetings, bookings, ranges, tasks with deadlines.

The move. Sort first. Almost every interval problem is one sort followed by one linear sweep. The only real decision is what to sort by.

The decision that solves the chapter

you want	sort by	why
merge overlapping intervals	start	any overlapping interval must begin inside the one you are building
most non-overlapping intervals to keep	end	finishing earliest leaves the most room for everything after
fewest removals to remove all overlaps	end	same problem, counted the other way
fewest points to stab every interval	end	same computation again
maximum concurrency / rooms	either — use a sweep line or a heap	you are counting, not choosing

Sorting by start is for merging. Sorting by end is for choosing. Getting that backwards is the single most common interval mistake, and it is worth carrying as one sentence.

The overlap condition

Two intervals [a,b] and [c,d] overlap when:

a \le d \quad\text{and}\quad c \le b

Each starts before the other ends. The negation is often easier to use: they are disjoint when b < c or d < a.

Always ask whether touching counts as overlapping. It flips < to <= and the problems disagree with each other:

• Merge Intervals — [1,4] and [4,5] do merge.
• Meeting Rooms and Non-overlapping Intervals — [1,2] and [2,3] do not conflict.

Two adjacent problems, opposite conventions. Ask every time.

The sweep line

The most transferable idea here. Turn each interval into two events and sort them:

events = []
for start, end in intervals:
    events.append((start, +1))
    events.append((end, -1))
events.sort()          # ties: (t, -1) sorts before (t, +1), so ends process first

count = best = 0
for _, delta in events:
    count += delta
    best = max(best, count)

The tie-break is deliberate. At equal times the -1 must come first, so a resource freed at time 10 is available to something starting at 10.

It solves maximum concurrency, car pooling, double bookings, the skyline problem, and capacity planning in real systems.

When the coordinate range is small and bounded, replace the sort with a difference array: add 1 at each start, subtract at each end, then take a prefix sum. O(n + T) instead of O(n \log n) — the bounded-values trick from 4.4.5.

The six problems

#	Problem	Sort by	The one insight
4.27.1	Insert Interval ★	already sorted	Three groups: before, overlapping, after
4.27.2	Merge Intervals ★	start	max(last_end, end) — a contained interval must not shrink it
4.27.3	Non-overlapping Intervals ★	end	Keep the most; remove the rest
4.27.4	Meeting Rooms ★	start	Sorted neighbours are enough
4.27.5	Meeting Rooms II ★	sweep or heap	The answer is the maximum concurrency
4.27.6	Minimum Interval per Query	both	Offline — sort the queries too

★ marks the Blind 75 subset.

The traps on this pattern

Forgetting max when merging. A fully contained interval would shrink the merged range.

Sorting by start when you should sort by end. Merging versus choosing.

Assuming the touching convention. Ask.

JavaScript's default sort. [[10,20],[9,15]] sorts as strings without a comparator.

Sorting when the input is already sorted. Insert Interval is O(n) precisely because it is not sorted again.

What the interviewer will push on

"Sort by start or by end, and why?" Merging versus choosing, with the exchange argument for the end case: finishing earliest leaves the most room.

"State the overlap condition." a <= d and c <= b.

"Does touching count?" Ask, and say why it matters.

"How do you count maximum concurrency?" The sweep line, with the tie-break explained.

"What if intervals arrive one at a time?" An ordered map or an interval tree, O(\log n) per insertion, instead of re-sorting.

One thing to volunteer: say the sort-by rule as your opening line. It is the whole chapter in one sentence, and it tells the interviewer you recognise the family rather than the problem.

Recall

• Sort first. Sort by start to merge; sort by end to choose the most non-overlapping.
• Overlap: a <= d and c <= b. Always ask whether touching counts — Merge Intervals says yes, Meeting Rooms says no.
• Merging needs max(last_end, end), or a contained interval shrinks the result.
• "Keep the most non-overlapping" is the activity selection greedy, proved by exchange: finishing earliest leaves the most room.
• Maximum concurrency = sweep line. Two events per interval, sorted, with ends processed before starts at equal times.
• Bounded coordinates → a difference array instead of a sort.
• Insert Interval is O(n) because the input is already sorted; Merge Intervals is O(n \log n) because it is not.
• When all queries are known in advance, sorting them (offline processing) often turns an impossible problem into a sweep.

Next: 4.27.1 Insert Interval — three groups, three loops, no branching.