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 []
intervals.sort(key=lambda pair: pair[0])
out = [list(intervals[0])]
for start, end in intervals[1:]:
last = out[-1]
if start <= last[1]: # overlap or touch
last[1] = max(last[1], end)
else:
out.append([start, end])
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
intervals.sort(key=lambda pair: pair[1])
kept = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end: # no conflict with the last one kept
kept += 1
last_end = end
return kept
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))
events.append((end, -1))
# 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.
events.sort()
running = best = 0
for _, delta in events:
running += delta
best = max(best, running)
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.
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 []
intervals.sort(key=lambda pair: pair[0])
merged: list[list[int]] = [list(intervals[0])] # copy, do not alias
for start, end in intervals[1:]:
last = merged[-1]
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])
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] |
[[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)
# Phase 1: everything that finishes before the new interval begins.
while i < n and intervals[i][1] < start:
out.append(intervals[i])
i += 1
# Phase 2: everything that overlaps. Widen, then emit once.
while i < n and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
out.append([start, end])
# Phase 3: everything that starts after the merged interval ends.
while i < n:
out.append(intervals[i])
i += 1
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 |
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
# Earliest finishing time first: it leaves the most room for what follows.
intervals.sort(key=lambda pair: pair[1])
kept = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end: # touching is allowed, so >= not >
kept += 1
last_end = end
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 |
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
intervals.sort(key=lambda pair: pair[0])
# Min-heap of end times. heap[0] is the room that frees up soonest.
rooms: list[int] = []
for start, end in intervals:
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)
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))
events.append((end, -1))
# 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
for _, delta in events:
running += delta
best = max(best, running)
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] |
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.