Problems built from start and end points, where one sort up front collapses every pairwise overlap check into a single pass down the line.
Problems built from start and end points, where one sort up front collapses every pairwise overlap check into a single pass down the line.
A calendar with 1,000 meetings has 499,500 possible pairs, and checking every pair for conflicts is exactly as slow as it sounds. The entire interval family rests on one fix: sort the intervals first, and every interval that can overlap yours becomes your immediate neighbor, so a single left-to-right sweep replaces the quadratic check. Meetings, hotel bookings, IP ranges, CPU reservations: they're all pairs of endpoints, and they all untangle the same way.
This page covers the three questions the family keeps asking. Can these be combined (merge)? How many survive together (scheduling)? And how many run at once (concurrency)? Each is one sort plus one sweep, differing only in the sort key and what the sweep tracks.
Two intervals [a, b] and [c, d] overlap exactly when a <= d and c <= b: each one starts before the other ends. After sorting by start time, the first half of that test is free, and overlap collapses to a single comparison: next.start <= current.end.
The one place this bites is touching endpoints. Do [1, 4] and [4, 5] overlap? With inclusive endpoints, yes: both contain the point 4, and Merge Intervals folds them into [1, 5]. In meeting-room scheduling, no: a meeting that ends at 4 hands the room to one that starts at 4 with zero conflict. Neither reading is wrong. The problem statement picks one, and your <= versus < has to match it.
Run the sweep on [[1, 3], [2, 6], [8, 10], [15, 18]], already sorted by start. The [1, 3] block opens. Next, [2, 6] starts at 2, inside the current block, so the block stretches to [1, 6]. Predict the rest before reading on: what happens to [8, 10] and [15, 18]?
Neither one merges. 8 is past the block's end of 6, so [1, 6] is emitted and [8, 10] opens a new block, and 15 is past 10, so the final answer reads [[1, 6], [8, 10], [15, 18]]. The detail that separates working code from almost-working code: extend the block's end with max, never plain assignment, because a nested interval like [2, 3] arriving inside [1, 10] must not drag the end backward from 10 to 3.
Merging sorts by start time so that overlaps pile onto the current block. The counting problems flip the key. To keep the maximum number of non-overlapping intervals (or delete the minimum number, same question in a mirror), sort by end time and greedily keep every interval that starts at or after the last kept end. The earliest-ending interval frees the most future, and the proof carries over unchanged from meeting scheduling.
You might think the choice of key is a detail. It's the whole answer. Sort the counting problems by start and a long early interval gets kept, blocking several short ones that together beat it. The interview tell: "merge" or "insert" means sort by start, "maximum number" or "minimum removals" means sort by end.
The third question ignores which intervals overlap and asks how many do so simultaneously: the minimum number of meeting rooms. Split the intervals into two sorted timelines, starts and ends, and walk them together. Each start is +1 room, each end is -1, and the answer is the highest the counter ever climbs. On [[0, 30], [5, 10], [15, 20]], the count goes up at 0 and 5, down at 10, up at 15, and peaks at 2: two rooms.
One tie-break carries the correctness: when an end and a start share a timestamp, process the end first, because a meeting ending at 10 frees its room for one starting at 10. Compare with ends[e] <= starts[s] and the handoff is free. Flip it to < and every back-to-back pair double-books a phantom room.
[1, 4] and [4, 5] touch or overlap before writing a single comparison. Inclusive endpoints merge them. Half-open scheduling treats them as back-to-back with no conflict. The difference is one equals sign.max(currentEnd, nextEnd) rather than assigning the newer value. Nested intervals like [1, 10] swallowing [2, 3] are exactly the case plain assignment corrupts.+1 and -1, and track the running maximum.Beyond the big three, two compositions recur. Interval List Intersections walks two already-sorted lists with two pointers: the intersection of the current pair is [max(starts), min(ends)] when that range is non-empty, and the pointer on the earlier-ending interval advances. Employee Free Time flattens everyone's schedules into one list, merges, and then reads the answer out of the gaps between merged blocks, a nice reminder that sometimes the output you want is the complement of the structure you built.
Recognition is easy in this family: the input is pairs of numbers representing ranges. The only real decision is which of the three questions is being asked, and the sort key plus sweep follows from that.
The bugs here are small and the stakes are whole answers. Five habits that prevent them:
<= that should have been <. Merge Intervals treats touching as overlapping. Meeting Rooms treats a meeting ending at 4 and one starting at 4 as compatible. State the convention before coding and the comparisons write themselves.Two checks before starting: after sorting by start, what single comparison decides whether two neighbors overlap, and why does Meeting Rooms II process an end before a start at the same timestamp? The problems below run merge first, then the end-time counting family, then concurrency:
Completed | Title | Status | Notes | Solution | |
|---|---|---|---|---|---|
merge_intervals.py
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
# Sorting puts every overlapping interval next to its neighbors
intervals.sort(key=lambda interval: interval[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last = merged[-1]
# Overlap: the next interval starts before the current one ends
if start <= last[1]:
# Extend with max so a nested interval can't shrink the end
last[1] = max(last[1], end)
else:
merged.append([start, end])
return mergedmeeting_rooms_ii.py
def min_meeting_rooms(intervals: list[list[int]]) -> int:
# Two sorted timelines: when meetings start, when they end
starts = sorted(interval[0] for interval in intervals)
ends = sorted(interval[1] for interval in intervals)
rooms = 0
busiest = 0
s = e = 0
while s < len(starts):
# Ends win ties: a room frees the instant a meeting ends
if ends[e] <= starts[s]:
rooms -= 1
e += 1
else:
rooms += 1
busiest = max(busiest, rooms)
s += 1
return busiest