Every interval problem is decided before the first line of logic, by the choice of sort key. Pick the right one and the rest is a single greedy pass.
Intervals show up as meetings, bookings, ranges of IDs, time windows on a chart. Unsorted, comparing every pair is O(n²). Sorted, each interval only ever needs to be compared with the one thing you are carrying forward, and the pass is O(n). The interesting content of this pattern is which key to sort by, because different questions want different keys.
| Signal | What it looks like |
|---|---|
| Pairs of numbers | [start, end], meetings, bookings, flight times, version ranges. |
| Overlap language | “merge”, “conflict”, “collide”, “can attend all”, “how many rooms”. |
| Coverage language | “total time covered”, “free gaps”, “the union of the ranges”. |
| Removal language | “minimum number to remove so the rest are disjoint”. |
a and b overlap when a.start < b.end and b.start < a.end. Equivalently, they are disjoint when one ends before the other begins. If they are already sorted by start, so a.start ≤ b.start, this collapses to a single test: b.start < a.end.[1, 3] and [3, 5] conflict? For merging ranges of integers, usually yes, so the test is ≤. For meeting rooms, usually no, because a meeting ending at 3 frees the room for one starting at 3, so the test is <. This single character decides several of the problems below. Ask, do not guess.After sorting by start time, every interval yet to be processed starts at or after the current one. So if the next interval does not overlap the range being built, no later interval can overlap it either, since they all start even later. The current range is finished and can be emitted. This is the loop invariant that makes the sweep correct in one pass.
This table is the pattern. Everything else is bookkeeping.
| Question | Sort by | Carry | Greedy rule |
|---|---|---|---|
| Merge overlapping ranges | start | the range being extended | Extend if it overlaps, else emit and restart. |
| Insert into a sorted list | already sorted by start | the growing new range | Absorb every range that touches it. |
| Keep the most non-overlapping | end | the last kept end time | Keep an interval if it starts at or after that end. |
| Max simultaneous overlap | start, plus a heap of ends | the earliest end still running | Reuse a room if its end is free, else open a new one. |
def sweep_merge(intervals: list[list[int]]) -> list[list[int]]:
"""Union of overlapping ranges."""
if not intervals:
return [] # nothing to merge
# pair[0]: the start. Sort by start so overlaps sit next to each other.
intervals.sort(key=lambda pair: pair[0])
out = [list(intervals[0])] # [0]: the first interval opens the output
# [1:]: skip index 0, it is already in out.
# Invariant: out is the merged union of every interval seen so far.
for start, end in intervals[1:]:
last = out[-1] # -1: the interval still being built
# last[1]: its end. A start at or before it means the two overlap.
if start <= last[1]: # overlap or touch
# max: never shrink. The new one may sit inside last.
last[1] = max(last[1], end)
else:
out.append([start, end]) # a gap: start a new merged interval
return out
max(last[1], end), not end. A short interval fully inside a long one must not shrink it.
def max_non_overlapping(intervals: list[list[int]]) -> int:
"""Largest set of mutually disjoint intervals."""
if not intervals:
return 0 # 0: no intervals, none can be kept
# pair[1]: the end. Earliest finish first leaves the most room after it.
intervals.sort(key=lambda pair: pair[1])
kept = 1 # 1: the earliest-finishing one is always kept
last_end = intervals[0][1] # [0][1]: end of that first kept interval
# [1:]: index 0 is already kept.
# Invariant: kept is the best count for intervals seen, ending at last_end.
for start, end in intervals[1:]:
if start >= last_end: # no conflict with the last one kept
kept += 1 # +1: take this interval too
last_end = end # the new finish line to beat
return kept
Reading the figure. Bars are drawn on a time axis in end order. Green bars are kept. The red dashed bar is dropped because it starts before last_end, the end of the last green bar.
def max_concurrent(intervals: list[list[int]]) -> int:
"""Peak number of intervals alive at any instant."""
events: list[tuple[int, int]] = []
for start, end in intervals:
events.append((start, +1)) # +1: one more interval is alive from here
events.append((end, -1)) # -1: one interval stops here
# At a tie, process the end (-1) before the start (+1), so a range that
# finishes exactly when another begins does not count as concurrent.
# Tuples sort by time first, then by delta, and -1 sorts before +1.
events.sort()
running = best = 0 # 0: nothing alive before the first event
# _: the time, not needed once sorted. delta: +1 or -1 from above.
# Invariant: running is how many intervals are alive just after this event.
for _, delta in events:
running += delta
best = max(best, running) # keep the peak
return best
The tuple sort does the tie-break for free, because -1 < +1. That is a neat detail worth pointing out in an interview.
Reading the figure. Blue bars are the intervals. Each start adds one and each end takes one away. The running row is the count after each event. The amber band is where three intervals overlap, the peak.
end instead of max(last_end, end) when merging. [[1, 10], [2, 3]] must merge to [1, 10], not [1, 3].< and ≤ for touching intervals. Ask once, then be consistent.out = [intervals[0]] aliases the caller’s list, and the merge then edits it in place. Copy with list(...).Given a list of intervals, merge all overlapping ones and return the non-overlapping intervals that cover exactly the same ground. For [[1,3],[2,6],[8,10],[15,18]] the answer is [[1,6],[8,10],[15,18]].
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
"""Merge every set of overlapping intervals into one.
Args:
intervals: Pairs [start, end] with start <= end, in any order.
Sorted in place as a side effect.
Returns:
Disjoint intervals in increasing order covering the same union.
Example:
>>> merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]])
[[1, 6], [8, 10], [15, 18]]
"""
if not intervals:
return [] # nothing to merge
# pair[0]: the start. Sorted by start, any overlap is with the last merged one.
intervals.sort(key=lambda pair: pair[0])
# [0]: the first interval seeds the output.
merged: list[list[int]] = [list(intervals[0])] # copy, do not alias
# [1:]: skip index 0, it is already in merged.
# Invariant: merged is the sorted, disjoint union of every interval seen.
for start, end in intervals[1:]:
last = merged[-1] # -1: the interval still being built
# last[1]: its end. A start at or before it means overlap.
if start <= last[1]:
# Overlaps or touches. Extend, but never shrink: the incoming
# interval may sit entirely inside the one we are building.
last[1] = max(last[1], end)
else:
merged.append([start, end]) # a gap: open a new merged interval
return merged
[[1,3],[2,6],[8,10],[15,18]], already sorted by start:
| incoming | last | test | result |
|---|---|---|---|
| [2, 6] | [1, 3] | 2 ≤ 3, overlap | last becomes [1, 6] |
| [8, 10] | [1, 6] | 8 > 6, disjoint | emit and open [8, 10] |
| [15, 18] | [8, 10] | 15 > 10, disjoint | emit and open [15, 18] |
Reading the figure. Amber is last, the range being built. Blue is the incoming interval. Green ranges are finished and emitted. An incoming start at or before the end of last extends it.
[[1, 10], [2, 3]]: must give [[1, 10]]. This is the max test.[[1, 4], [4, 5]]: with ≤ they merge to [[1, 5]]. Confirm which behaviour is wanted.You are given a list of already sorted, non-overlapping intervals and one new interval. Insert it, merging where needed, and return the result still sorted and non-overlapping.
while loops rather than one loop with flags is what makes it readable.def insert_interval(
intervals: list[list[int]], new_interval: list[int]
) -> list[list[int]]:
"""Insert one interval into a sorted, disjoint list, merging as needed.
Args:
intervals: Sorted, pairwise non-overlapping [start, end] pairs.
new_interval: The interval to add.
Returns:
A new list, still sorted and non-overlapping.
Example:
>>> insert_interval([[1, 3], [6, 9]], [2, 5])
[[1, 5], [6, 9]]
"""
start, end = new_interval
out: list[list[int]] = []
i, n = 0, len(intervals) # 0: scan from the first interval
# Phase 1: everything that finishes before the new interval begins.
# [i][1]: the end of interval i. It ends before start, so no overlap.
while i < n and intervals[i][1] < start:
out.append(intervals[i])
i += 1 # +1: move to the next interval
# Phase 2: everything that overlaps. Widen, then emit once.
# [i][0]: the start of interval i. At or before end means overlap.
while i < n and intervals[i][0] <= end:
start = min(start, intervals[i][0]) # [0]: grow left to the earlier start
end = max(end, intervals[i][1]) # [1]: grow right to the later end
i += 1 # +1: this one is absorbed, move on
out.append([start, end])
# Phase 3: everything that starts after the merged interval ends.
while i < n:
out.append(intervals[i])
i += 1 # +1: move to the next interval
return out
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], inserting [4, 8]:
| Phase | Handles | State |
|---|---|---|
| 1 | [1, 2] | 2 < 4, copied |
| 2 | [3, 5], [6, 7], [8, 10] | new interval grows 4→3 then 8→10, emits [3, 10] |
| 3 | [12, 16] | copied |
Reading the figure. Blue bars are copied as they are. Amber is the new interval as it grows. Red dashed bars are absorbed into it. Green is the result, still sorted and non-overlapping.
Result: [[1,2],[3,10],[12,16]].
[2, 3] into [[1, 10]]: phase 2 widens it back out to [1, 10]. Verify this case, it is the one people get wrong.Given a list of intervals, return the minimum number to remove so that the rest are pairwise non-overlapping.
len(intervals) - kept.f be the interval with the earliest end time. Take any optimal solution OPT that does not contain f, and let g be the first interval in OPT. Since f ends no later than g, swapping g for f cannot create a new conflict with anything later in OPT. So there is an optimal solution containing f. Remove f and everything it conflicts with, and repeat the argument on what remains. Greedy by earliest end is therefore optimal.[[1, 100], [2, 3], [4, 5]]. Sorted by start, the greedy keeps [1, 100] first and then must drop both others, keeping 1. Sorted by end, it keeps [2, 3] and [4, 5], keeping 2. Have this counterexample ready; interviewers ask for it.def erase_overlap_intervals(intervals: list[list[int]]) -> int:
"""Fewest intervals to delete so the remainder are pairwise disjoint.
Args:
intervals: Pairs [start, end]. Sorted in place as a side effect.
Returns:
The number of intervals that must be removed.
Example:
>>> erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]])
1
"""
if not intervals:
return 0 # 0: nothing to remove
# Earliest finishing time first: it leaves the most room for what follows.
intervals.sort(key=lambda pair: pair[1]) # pair[1]: the end
kept = 1 # 1: the earliest-finishing one is always kept
last_end = intervals[0][1] # [0][1]: end of that first kept interval
# [1:]: index 0 is already kept.
# Invariant: kept is the most disjoint intervals among those seen so far.
for start, end in intervals[1:]:
if start >= last_end: # touching is allowed, so >= not >
kept += 1 # +1: keep this one too
last_end = end # the new finish line to beat
# Removing the most is the same as keeping the most.
return len(intervals) - kept
[[1,2],[2,3],[3,4],[1,3]] sorted by end becomes [[1,2],[1,3],[2,3],[3,4]]:
| interval | last_end | decision | kept |
|---|---|---|---|
| [1, 2] | — | keep, it is the seed | 1 |
| [1, 3] | 2 | 1 < 2, conflict, drop | 1 |
| [2, 3] | 2 | 2 ≥ 2, keep | 2 |
| [3, 4] | 3 | 3 ≥ 3, keep | 3 |
Reading the figure. Rows are in end order. The amber line is last_end when that row is checked. A bar that starts left of the line overlaps and turns red. Green bars are kept.
Kept 3 of 4, so remove 1.
0.n - 1.0.>=. Confirm this reading with the interviewer.Given meeting time intervals, return the minimum number of conference rooms needed to hold them all. A meeting that ends at time t frees its room for a meeting starting at t.
+1 at its start and a -1 at its end, sort all events, and track the running total. Simpler, and the one to reach for if the heap feels heavy.import heapq
def min_meeting_rooms(intervals: list[list[int]]) -> int:
"""Minimum rooms needed so no two meetings share a room.
Args:
intervals: Pairs [start, end] with start < end.
Sorted in place as a side effect.
Returns:
The peak number of simultaneously running meetings.
Example:
>>> min_meeting_rooms([[0, 30], [5, 10], [15, 20]])
2
"""
if not intervals:
return 0 # 0: no meetings, no rooms
# pair[0]: the start. Hand out rooms in the order meetings begin.
intervals.sort(key=lambda pair: pair[0])
# Min-heap of end times. heap[0] is the room that frees up soonest.
rooms: list[int] = []
# Invariant: rooms holds one end time per room opened so far.
for start, end in intervals:
# rooms[0]: the earliest end. At or before start means that room is free.
if rooms and rooms[0] <= start:
heapq.heapreplace(rooms, end) # reuse: pop the free room, push ours
else:
heapq.heappush(rooms, end) # every room is busy, open one more
return len(rooms) # rooms never close, so the size is the peak
heapreplace is one sift instead of the two you get from heappop followed by heappush. Same result, half the work, and it reads as the single action it is.def min_meeting_rooms_sweep(intervals: list[list[int]]) -> int:
"""Same answer via a sweep over start and end events."""
events: list[tuple[int, int]] = []
for start, end in intervals:
events.append((start, 1)) # 1: a meeting starts, one more room in use
events.append((end, -1)) # -1: a meeting ends, one room frees up
# Sorting tuples puts (t, -1) before (t, 1), so a room freed at time t
# is available to a meeting starting at t. That is the tie-break we want.
events.sort()
running = best = 0 # 0: no rooms in use before the first event
# _: the time, not needed once sorted. delta: 1 or -1 from above.
# Invariant: running is the rooms in use just after this event.
for _, delta in events:
running += delta
best = max(best, running) # keep the peak
return best
[[0, 30], [5, 10], [15, 20]], heap version:
| meeting | rooms[0] | decision | heap after |
|---|---|---|---|
| [0, 30] | — | open a room | [30] |
| [5, 10] | 30 | 30 > 5, still busy, open | [10, 30] |
| [15, 20] | 10 | 10 ≤ 15, reuse | [20, 30] |
Reading the figure. Blue bars open a room. The green bar reuses a room, since the earliest end in the heap was 10 and 10 ≤ 15. The amber line marks time 15. The boxes show the heap of end times after each meeting.
Two rooms.
Both solutions are dominated by the sort. The heap holds at most one entry per concurrent meeting.
0 rooms.[[1, 5], [5, 9]]: one room, because of ≤ in the heap version and the tuple tie-break in the sweep. This is the case that separates the two readings of “overlap”.n rooms.next.start < current.end. Everything else is bookkeeping.max(last_end, end), or nested intervals shrink the result.Pattern 5, Cyclic Sort, is the other “rearrange in place” pattern. Where intervals lean on sorting, cyclic sort exploits a much stronger promise: the values are drawn from a known bounded range, so each one already knows where it belongs.