Intervals: Merge, Insert, Sweep Line & Scheduling
An interval is a pair of numbers that describes a stretch of a line: a meeting from 9:00 to 10:30, a TCP segment covering bytes 4096 to 8191, a gene on a chromosome from position 1,200,000 to 1,210,000. Interval problems look like a dozen unrelated puzzles until you notice that almost all of them are solved by one of three moves: sort by start, sweep a line across the time axis, or keep a min-heap of end times. This lesson builds those three moves from first principles, proves why they work, and then applies them to every classic variant.
The payoff is unusual. Most pattern pages teach you to recognise one shape of problem. Intervals are a family where the recognition is easy ("there are start and end times") and the hard part is picking the right move. By the end you should be able to look at a new interval problem and say, within a minute, "that is merge", "that is activity selection", or "that is a sweep with an active set" — and know what breaks when the intervals are closed instead of half-open.
Why this exists
Scheduling is one of the oldest problems in computing. The first time-sharing operating systems in the 1960s had to decide which jobs could run together; the first calendar programs had to detect double bookings; compilers since the 1980s have had to assign a finite set of CPU registers to variables whose lifetimes are intervals in the instruction stream. All of these reduce to questions about how a set of intervals overlaps itself: Do any two overlap? What is the union? What is the deepest point of overlap? What is the largest set of mutually disjoint intervals?
The structural fact that makes intervals tractable is that they live on a line. On a line, "before" and "after" are total orders, so a set of intervals has a canonical sorted order, and once sorted, every overlap question becomes local: an interval can only interact with its immediate neighbours in the sort. That is not true for rectangles in a plane or boxes in space (which need segment trees, k-d trees and sweep-plus-structure techniques), and it is exactly why so many interval problems collapse to for the sort plus a linear pass.
The sweep line idea — move a vertical line from left to right, maintain the set of intervals it currently cuts, and only do work at the finitely many points where that set changes — comes from computational geometry (Shamos and Hoey, 1976; the textbook treatment is de Berg et al., Computational Geometry, chapter 2). It is the general tool; sort-and-merge and the heap of end times are its two most common specialisations.
Interval problems appear in production more than almost any other pattern on this course: calendar free/busy computation, range locks in databases, memory allocator coalescing, LSM-tree compaction, time-series partition pruning, register allocation, and genomics overlap queries. The Real-world uses section walks through each.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
"intervals", "ranges", "segments", [start, end] pairs | sort by start, then one linear pass |
| "merge overlapping", "union of", "coalesce", "consolidate" | merge intervals |
| "insert a new interval into a sorted list" | insert interval (three phases: before / overlapping / after) |
| "meetings", "can a person attend all", "any conflict?" | sort by start, check next.start < cur.end |
| "minimum number of rooms / platforms / machines / lanes" | interval partitioning: min-heap of end times, or sweep line; answer = max depth |
| "maximum number of non-overlapping", "remove the fewest to make disjoint" | activity selection: greedy by earliest end |
| "points covering intervals", "fewest arrows / stabs / probes" | sort by end, greedy stab at the end of the first uncovered interval |
| "timeline", "at any moment", "peak concurrent", "how many active at time t" | sweep line with +1/−1 events |
| "skyline", "visible height", "max over active set" | sweep line with a max-heap and lazy deletion |
| "total covered length", "how much time is busy" | merge, then sum lengths |
| "free time", "gaps", "idle periods" | merge, then read the gaps between consecutive merged intervals |
| "passengers on/off", "range add, then query every point" | difference array (Prefix Sums & Difference Arrays) |
| "two sorted lists of intervals, find the common parts" | two pointers (Two Pointers) |
| "book if no triple overlap", "online insertions and queries" | difference map (ordered map sweep) or a balanced tree of disjoint intervals |
| intervals with weights/profits and "maximise total" | not greedy — weighted interval scheduling DP (Module 6) |
Intuition & first principles
Representing an interval
An interval has a start and an end with . The question that trips people up is whether the endpoints are in the interval:
- Closed : both endpoints included. "Balloons from x=1 to x=6" in LeetCode 452 are closed: an arrow at 6 pops a balloon ending at 6.
- Open : neither endpoint included. Rare in programming problems.
- Half-open : start included, end excluded. This is the convention of Python's
range, C++ iterator pairs, byte ranges in file systems and almost every calendar system: a meeting from 9:00 to 10:00 and another from 10:00 to 11:00 do not conflict.
The convention decides what touching means. Intervals and share the single point 5. Under closed semantics they overlap (a person cannot be in two meetings at the instant 5). Under half-open semantics and are disjoint, because 5 belongs only to the second. Problem statements usually tell you ("meetings may start at the exact time another ends"); when they do not, the sample tests will. Always decide this before writing the comparison, because it changes < to <= in exactly one place and that place is where bugs hide.
Half-open is the safer default
Half-open intervals compose: and union to with no double-counted point, lengths are simply , and adjacent ranges partition a line with no gaps and no overlaps. When you design an API, use half-open. When you solve a stated problem, use whatever the problem says.
The overlap test, and why it is correct
Two intervals and (closed) overlap when they share at least one point. The compact test is:
A.start <= B.end && B.start <= A.end
It is easier to prove by looking at the complement. Two intervals on a line are disjoint in exactly two ways: lies entirely to the left of , or entirely to the right. "Entirely to the left" means 's last point precedes 's first point: . "Entirely to the right" means . So
Negate with De Morgan: , which is the test above. There is no third case because the line is totally ordered: if is neither left of nor right of , some point of sits at or between the endpoints of .
For half-open intervals, "disjoint" becomes (touching counts as disjoint), so the overlap test tightens to strict inequalities: A.start < B.end && B.start < A.end.
A second useful form: the intersection of two intervals is and they overlap iff that intersection is non-empty, i.e. (strict < for half-open). This form generalises to the "intersection of two interval lists" problem below.
Sorting by start: the master move
Every classic interval algorithm begins with sort by start. Here is the claim that justifies it, and the proof.
Claim. Process intervals in order of increasing start, maintaining a current merged block cur (the union of the most recent run of overlapping intervals). Then the next interval overlaps the union of all intervals processed so far if and only if . Overlap against the entire history is a one-comparison local check.
Proof. Let the processed intervals, after merging, be disjoint blocks , emitted in order; each for was closed off because some later interval started strictly after 's end, so . In particular, for every . Because input is sorted by start, (cur's start is the start of some already-processed interval). Therefore for every : cannot overlap any closed block. The only candidate is cur, and since , overlap with cur reduces to .
The same proof shows why sorting by end is the right move for a different family: when you are greedily selecting disjoint intervals (activity selection), you want the chosen interval to end as early as possible so that it constrains the future least. Sorting by start answers "what does this interval collide with?"; sorting by end answers "which interval should I commit to?". Picking the wrong sort for the problem is the single most common interval bug and gets its own entry under Pitfalls.
Mechanics
Merge intervals
Input: a list of intervals. Output: the minimal list of disjoint intervals with the same union.
flowchart TD
A["Sort intervals by start"] --> B["cur = first interval"]
B --> C{"another interval?"}
C -->|"no"| D["emit cur, done"]
C -->|"yes"| E{"next.start <= cur.end ?"}
E -->|"yes: overlaps or touches"| F["cur.end = max(cur.end, next.end)"]
E -->|"no: gap"| G["emit cur, then cur = next"]
F --> C
G --> C
Note the max in the extend step. Beginners write cur.end = next.end, which is wrong when the next interval is contained in the current one: merging with must leave the end at 10.
Trace on [[1,3],[2,6],[8,10],[15,18],[17,20]] (already sorted by start):
| Next interval | Test | Action | cur after | Output so far |
|---|---|---|---|---|
| — | — | start with first | [1, 3] | [] |
[2, 6] | 2 ≤ 3 | extend end to max(3, 6) = 6 | [1, 6] | [] |
[8, 10] | 8 > 6 | emit cur, start new | [8, 10] | [[1, 6]] |
[15, 18] | 15 > 10 | emit cur, start new | [15, 18] | [[1, 6], [8, 10]] |
[17, 20] | 17 ≤ 18 | extend end to max(18, 20) = 20 | [15, 20] | [[1, 6], [8, 10]] |
| (end) | — | emit cur | — | [[1, 6], [8, 10], [15, 20]] |
With closed semantics [1,4] and [4,5] merge into [1,5] (the test is <=). If the problem used half-open intervals you would change the test to < and they would stay separate.
Insert interval
Given a list of disjoint intervals already sorted by start and a new interval , produce the sorted disjoint list after inserting and merging whatever it overlaps. The input is sorted, so do not re-sort: a single pass in three phases is .
flowchart LR
P1["Phase 1: intervals finishing before N.start<br/>copy unchanged"] --> P2["Phase 2: intervals with start <= N.end<br/>absorb: N = [min starts, max ends]"]
P2 --> P3["Phase 3: everything left<br/>copy unchanged"]
Phase 1 stops at the first interval that could touch (its end is ). Phase 2 consumes every interval whose start is , widening as it goes; because the list is sorted and disjoint, these intervals are contiguous in the list. Phase 3 copies the rest. The three phases visit each input interval exactly once.
Insert [4, 8] into [[1,2],[3,5],[6,7],[8,10],[12,16]]: phase 1 copies [1,2] (2 < 4); phase 2 absorbs [3,5], [6,7], [8,10] (starts 3, 6, 8 are all ≤ 8, and the end grows to 10), giving [3,10]; phase 3 copies [12,16]. Result: [[1,2],[3,10],[12,16]].
Intersection of two sorted interval lists
Two lists and , each internally disjoint and sorted. Report every intersection. This is a textbook two-pointer walk: compare and , emit if non-empty, then advance the pointer whose interval ends first — that interval cannot intersect anything further in the other list, because everything further starts after the other list's current interval starts, and the finished interval already ends before the other's end. .
Activity selection: maximum set of non-overlapping intervals
Choose as many mutually disjoint intervals as possible. Sort by end, take the first, then repeatedly take the next interval whose start is at or after the end of the last chosen one. The companion problem "remove the fewest intervals to make the rest disjoint" (LeetCode 435) has the same answer: minus the size of the maximum disjoint set.
The exchange argument is in Greedy Algorithms; the one-paragraph version is in Correctness below.
Meeting Rooms I: can one person attend everything?
Sort by start; for consecutive intervals check next.start < cur.end (closed: <=). Any violation is a conflict. Correct by the master-move claim: a conflict with anything earlier is a conflict with the latest-ending interval seen so far, and since the list is sorted and we never merge, the latest interval is the previous one only if the previous intervals are disjoint — which is exactly what we are verifying as we go. for the sort.
Meeting Rooms II: minimum number of rooms
The key fact: the minimum number of rooms equals the depth of the interval set — the maximum number of intervals that contain a common point. Two ways to compute it.
Solution A — min-heap of end times. Sort by start. Keep a min-heap of the end times of meetings currently assigned to rooms. For each meeting in start order: if the heap's smallest end time is this meeting's start (half-open: the room is free exactly when the previous meeting ends), pop it — that room is reused; then push this meeting's end. The heap size at the end is the number of rooms ever needed. Equivalent to "assign to any free room, else open a new one".
Trace on [[0,30],[5,10],[15,20],[12,25]], sorted by start → [0,30], [5,10], [12,25], [15,20]:
| Interval | Heap before (sorted) | Pop? | Heap after | Rooms in use |
|---|---|---|---|---|
[0, 30] | [] | no (empty) | [30] | 1 |
[5, 10] | [30] | no (30 > 5) | [10, 30] | 2 |
[12, 25] | [10, 30] | pop 10 (10 ≤ 12: that room is free) | [25, 30] | 2 |
[15, 20] | [25, 30] | no (25 > 15) | [20, 25, 30] | 3 |
Answer: 3 rooms.
Solution B — sweep line. Turn every interval into two events, and . Sort events by time; at equal times, process before for half-open intervals. Walk the events keeping a running count; the maximum running count is the depth.
flowchart LR
I["intervals [s, e)"] --> EV["events: (s, +1) and (e, -1)"]
EV --> S["sort by (time, delta)<br/>-1 sorts before +1"]
S --> R["running count += delta"]
R --> M["answer = max running count"]
Trace on the same input. Events sorted: (0,+1) (5,+1) (10,−1) (12,+1) (15,+1) (20,−1) (25,−1) (30,−1).
| Time | Delta | Running count | Max so far |
|---|---|---|---|
| 0 | +1 | 1 | 1 |
| 5 | +1 | 2 | 2 |
| 10 | −1 | 1 | 2 |
| 12 | +1 | 2 | 2 |
| 15 | +1 | 3 | 3 |
| 20 | −1 | 2 | 3 |
| 25 | −1 | 1 | 3 |
| 30 | −1 | 0 | 3 |
Answer: 3. Both solutions agree, and a brute-force check — count intervals containing each endpoint — also gives 3.
Why the tie-break matters, with proof. Under half-open semantics, point is covered by iff . So the number of intervals covering is
If we sort events by with , then after processing all events with time the running count is exactly , because every start has contributed and every end has contributed . We also need the intermediate values (after some but not all events at time ) never to exceed a real coverage value. Processing the events first at time drives the count from (coverage just before ) down to , then each raises it, finishing at . Every intermediate value lies between a lower number and , so the maximum of the whole walk equals , the true depth. If instead we processed first, the count at time would momentarily reach , which counts a meeting that ends at and a meeting that starts at as simultaneous — wrong for half-open intervals, and it would report 2 rooms for [[1,5],[5,10]] instead of 1. For closed intervals the touching pair really does overlap, so you reverse the tie-break ( before ).
The heap solution encodes the same choice in heap.top() <= start (half-open) versus heap.top() < start (closed).
Sweep line in general
The sweep line is a schema, not one algorithm:
- Convert each interval into events at its endpoints.
- Sort events (time, then a tie-break you have proven correct).
- Walk the events, maintaining an active set — the intervals the sweep line currently cuts — in whatever structure answers your query: a counter, a heap, a balanced tree, a multiset.
- Answer the question at each event or between consecutive events.
Three instances beyond meeting rooms:
Skyline (LeetCode 218). Buildings are intervals with heights. The skyline is the upper envelope: at each , the max height of the active set. Active set = max-heap of (height, right edge). Sort events so that at the same starts come before ends, and among starts taller comes first. At each event, first pop heap entries whose right edge is (lazy deletion: we never remove from the middle of a heap, we just discard stale tops when they surface), then push the new building if this is a start, then read the top. Emit a key point whenever the current max height changes. In C++ a std::multiset<int> of heights with true deletion is the alternative. .
Union length / covered points. Total length of the union of intervals: merge, then sum end − start of each merged block. With a sweep: track when the running count goes from 0 to 1 (an uncovered-to-covered transition) and from 1 to 0, summing the lengths of covered stretches. For "how many integer points are covered at least once" with closed integer intervals, the answer is the sum over merged blocks of end − start + 1.
Number of points covered by intervals, or maximum overlap with weights (car pooling with passenger counts, bandwidth reservations): the delta is the weight instead of . When the coordinates are small integers, the sorted event walk becomes a difference array: diff[s] += w; diff[e] -= w, then a prefix sum. See Prefix Sums & Difference Arrays. LeetCode 1094 Car Pooling is exactly this with stops in .
Employee free time
Each employee has a sorted list of busy intervals; find the gaps common to everyone. Flatten all lists into one, sort by start, merge. The free intervals are the gaps between consecutive merged blocks (the problem excludes the unbounded gaps before the first and after the last). A -way merge with a heap of iterators gives the same result in if the per-employee lists are already sorted; sorting everything is and usually fine.
Minimum arrows to burst balloons
Balloons are closed intervals on the x-axis; one arrow at bursts every balloon containing . Fewest arrows: sort by end, shoot at the end of the first balloon, skip every balloon whose start is that , repeat with the next unburst balloon. This is the dual of activity selection — the minimum number of points stabbing all intervals equals the maximum number of pairwise-disjoint intervals (a special case of the interval-graph clique-cover / independent-set duality), and the same earliest-end greedy finds both.
Interval scheduling maximisation and weighted interval scheduling
Unweighted: activity selection, above. Weighted (each interval has a value, maximise total value of a disjoint subset): greedy fails — a long valuable interval can beat two short ones. The solution is dynamic programming over intervals sorted by end: where is the last interval ending at or before 's start, found by binary search. . This is a Module 6 (Dynamic Programming) topic; it appears here so you recognise the trigger word weighted and stop reaching for greedy.
Interval partitioning and the depth lower bound
Interval partitioning asks for the minimum number of resources (rooms, classrooms, platforms, registers) so that no two overlapping intervals share one. It is Meeting Rooms II under another name. Depth — the maximum number of intervals sharing a point — is an obvious lower bound (those intervals need distinct resources), and the remarkable fact is that resources always suffice; the greedy heap algorithm achieves it. Proof in Correctness. Interval graphs are therefore perfect: chromatic number equals clique number.
Data structures for intervals
When intervals arrive and leave dynamically, or you need many queries ("which stored intervals overlap ?"), a sorted list stops being enough:
- Interval tree (CLRS §14.3): a balanced BST keyed on start where each node also stores the maximum end in its subtree, giving "find any overlapping interval" and enumeration. Module 3's Spatial Trees page (wave 2) covers interval trees, k-d trees and R-trees.
- Segment tree over the compressed coordinates: supports "add 1 to every point in " and "max over all points" in , which turns Calendar III and dynamic depth queries into logarithmic operations. Module 3's Segment Trees in Depth (wave 2) builds it; Advanced Data Structures has the overview today.
- Ordered map of disjoint intervals (
TreeMap,std::map,sortedcontainers): the basis of range modules and "data stream as disjoint intervals".
Calendar booking I, II, III
- My Calendar I (no double booking): keep the booked intervals; a new booking succeeds iff it overlaps none. Brute list scan is per booking; a
TreeMap/std::mapkeyed by start lets you check only the predecessor and successor in . - My Calendar II (no triple booking): keep two lists —
bookedandoverlaps(the pairwise intersections of booked intervals). Reject if the new interval intersects anything inoverlaps; otherwise add its intersections withbookedtooverlapsand add it tobooked. per booking. - My Calendar III (return the maximum such that some point is -booked after each insertion): a difference map — an ordered map from time to delta,
diff[s] += 1; diff[e] -= 1— then sweep the map in key order to find the maximum running sum. per booking, total; a dynamic segment tree makes it per booking.
Range module
"Add a range, remove a range, query whether a range is fully covered." Keep an ordered map of disjoint half-open intervals. add(l, r): find every stored interval that touches or overlaps , merge them all with it, store the result. remove(l, r): find every stored interval overlapping , delete them, and re-insert the (up to two) pieces that stick out to the left of or right of . query(l, r): find the stored interval whose start is the greatest and check it reaches . Each operation is where is the number of intervals touched, and because every operation adds at most two intervals net, the amortised cost is logarithmic.
The ladder: brute force → better → optimal
Take Meeting Rooms II (minimum rooms) as the worked example.
Rung 1 — pairwise simulation, . Sort by start. For each meeting, scan all previously assigned rooms and take any whose last meeting ended at or before this start; else open a new room. Each meeting scans up to rooms, so , space. It is correct, and it is the version to write first in an interview if you are unsure — then improve it.
Rung 2 — min-heap of end times, . The scan in rung 1 asks only "is there any room whose end start?", and the room with the smallest end answers it. Replace the room list with a min-heap keyed by end time: peek in , pop/push in . Total for the sort plus for heap operations, extra space. The heap also tells you which room each meeting goes into, which the sweep does not.
Rung 3 — sweep line, . Same asymptotics, different constants and different generality. events to sort instead of intervals, but then only a counter — no heap, no allocation, very cache-friendly. It generalises to weights, to "how many intervals cover point for every ", and to "which time has the peak". It does not produce a room assignment. When coordinates are small integers, the sort disappears entirely and the sweep becomes an difference array.
| Rung | Idea | Time | Extra space | Gives assignment? | Generalises to |
|---|---|---|---|---|---|
| 1 | scan every room | yes | — | ||
| 2 | min-heap of ends | yes | online arrivals in start order | ||
| 3 | sweep ±1 events | ( with difference array) | no | weights, per-point coverage, peak time |
Both rungs 2 and 3 are optimal in the comparison model: computing the depth requires knowing the sorted order of endpoints in the worst case (an lower bound via reduction from element distinctness), so the sort is the floor.
Correctness
Merge intervals: loop invariant
Sort by start. Let the processed prefix be . Invariant: after processing , the emitted list out together with cur is a sequence of pairwise-disjoint intervals whose union equals , and every interval in out ends strictly before cur.start.
Initialisation: out = [], cur = I_1. Trivially true.
Maintenance: process with (sorted). Case : overlaps or touches cur, so is a single interval; replacing cur with it keeps the union exact, keeps disjointness (the new cur still starts after every out end), and preserves "out ends before cur.start" since cur.start is unchanged. Case : by the master-move claim, is disjoint from cur and from every interval in out (all of which end before cur.start ); emitting cur and setting cur = I_{i+1} keeps the invariant, and the new cur.start = s > the end of the just-emitted cur.
Termination: after , emit cur. The output is a disjoint list with the right union. It is also minimal: two adjacent output intervals have a strict gap between them (the second starts strictly after the first ends), so no further merging is possible.
Activity selection: exchange argument (brief)
Let be the interval with the earliest end, and any optimal disjoint set. If , let be the interval in with the earliest end; then , so is disjoint from every other member of (they all start at or after ). Swap for : still disjoint, same size, now contains the greedy choice. Repeat on the sub-problem of intervals starting at or after . The full argument, with the formula, is on the Greedy page.
Rooms = depth, both directions
Let be the depth (max number of intervals containing one point) and the number of rooms the heap greedy uses.
(any schedule). At the point where intervals overlap, those meetings are all in progress and no room can hold two of them. Pigeonhole: at least rooms.
(the greedy). Consider the moment the greedy opens room number , while processing meeting in start order. It opened a new room because every one of the existing rooms held a meeting whose end is . Each of those meetings started at or before (they were processed earlier in start order). So all of them, plus itself, contain the point : depth at is at least . Hence .
This is the interval partitioning result in Kleinberg & Tardos, Algorithm Design, §4.1, and it is why the sweep (which computes ) and the heap (which computes ) always agree.
Complexity
| Problem | Time | Space (beyond output) | Notes |
|---|---|---|---|
| Overlap test, two intervals | — | ||
| Merge intervals | in place after sort, typical | if input is already sorted | |
| Insert interval (sorted input) | output | no sort | |
| Intersect two sorted lists | two pointers | ||
| Activity selection / min arrows | sort by end | ||
| Meeting Rooms I | — | ||
| Meeting Rooms II (heap) | = answer | ||
| Meeting Rooms II (sweep) | events | with small integer coordinates | |
| Skyline | lazy-deletion heap | ||
| Calendar III, difference map | per booking | with a segment tree | |
| Weighted interval scheduling | DP, Module 6 |
Best, average and worst case coincide for all of these — the sort dominates and comparison sorts are on all inputs for the standard library algorithms; the subsequent passes are unconditionally.
Constants and cache. The sweep over events sorted as flat tuples is extremely cache-friendly: one sequential pass after the sort. The heap solution does pointer-chasing per meeting but is usually tiny, so its heap operations are near-free in practice; its sort is on items rather than . In Python the tuple sort is the hot spot; competitive programmers encode each event as the single integer time * 2 + (delta == +1) so the sort runs on flat ints.
Implementation
The canonical four: merge, insert, minimum rooms with a heap, and maximum overlap with a sweep. All treat intervals as half-open for the room problems (a room is free at the instant its meeting ends) and closed for merging (touching intervals merge), matching LeetCode 56/57/253. The test data is identical in all four languages.
import heapq
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
"""Closed intervals; touching intervals merge. O(n log n)."""
if not intervals:
return []
out: list[list[int]] = []
for s, e in sorted(intervals):
if out and s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else:
out.append([s, e])
return out
def insert_interval(intervals: list[list[int]], new: list[int]) -> list[list[int]]:
"""intervals is sorted and disjoint. Three phases, O(n)."""
s, e = new
out: list[list[int]] = []
i, n = 0, len(intervals)
while i < n and intervals[i][1] < s: # phase 1: entirely before
out.append(list(intervals[i]))
i += 1
while i < n and intervals[i][0] <= e: # phase 2: overlapping, absorb
s = min(s, intervals[i][0])
e = max(e, intervals[i][1])
i += 1
out.append([s, e])
while i < n: # phase 3: entirely after
out.append(list(intervals[i]))
i += 1
return out
def min_meeting_rooms(intervals: list[list[int]]) -> int:
"""Half-open [s, e): a room is free at time e. Min-heap of end times."""
ends: list[int] = []
for s, e in sorted(intervals):
if ends and ends[0] <= s:
heapq.heapreplace(ends, e) # reuse the room that frees earliest
else:
heapq.heappush(ends, e) # open a new room
return len(ends)
def max_overlap(intervals: list[list[int]]) -> int:
"""Sweep line over half-open intervals; -1 sorts before +1 at ties."""
events: list[tuple[int, int]] = []
for s, e in intervals:
events.append((s, 1))
events.append((e, -1))
events.sort()
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
if __name__ == "__main__":
assert merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18], [17, 20]]) == [[1, 6], [8, 10], [15, 20]]
assert merge_intervals([[1, 4], [4, 5]]) == [[1, 5]]
assert merge_intervals([[1, 10], [2, 3]]) == [[1, 10]]
assert merge_intervals([]) == []
assert insert_interval([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]]
assert insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) == [[1, 2], [3, 10], [12, 16]]
assert insert_interval([], [5, 7]) == [[5, 7]]
rooms_tests = [([[0, 30], [5, 10], [15, 20]], 2),
([[0, 30], [5, 10], [15, 20], [12, 25]], 3),
([[7, 10], [2, 4]], 1),
([[1, 5], [5, 10]], 1),
([], 0)]
for data, want in rooms_tests:
assert min_meeting_rooms(data) == want, (data, want)
assert max_overlap(data) == want, (data, want)
print("ALL TESTS PASSED")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Intervals {
/** Closed intervals; touching intervals merge. O(n log n). */
static int[][] mergeIntervals(int[][] intervals) {
if (intervals.length == 0) return new int[0][];
int[][] a = intervals.clone();
Arrays.sort(a, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
List<int[]> out = new ArrayList<>();
int[] cur = a[0].clone();
for (int i = 1; i < a.length; i++) {
if (a[i][0] <= cur[1]) cur[1] = Math.max(cur[1], a[i][1]);
else { out.add(cur); cur = a[i].clone(); }
}
out.add(cur);
return out.toArray(new int[0][]);
}
/** intervals is sorted and disjoint. Three phases, O(n). */
static int[][] insertInterval(int[][] intervals, int[] nw) {
int s = nw[0], e = nw[1], i = 0, n = intervals.length;
List<int[]> out = new ArrayList<>();
while (i < n && intervals[i][1] < s) out.add(intervals[i++].clone());
while (i < n && intervals[i][0] <= e) {
s = Math.min(s, intervals[i][0]);
e = Math.max(e, intervals[i][1]);
i++;
}
out.add(new int[]{s, e});
while (i < n) out.add(intervals[i++].clone());
return out.toArray(new int[0][]);
}
/** Half-open [s, e): a room is free at time e. Min-heap of end times. */
static int minMeetingRooms(int[][] intervals) {
int[][] a = intervals.clone();
Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
PriorityQueue<Integer> ends = new PriorityQueue<>();
for (int[] iv : a) {
if (!ends.isEmpty() && ends.peek() <= iv[0]) ends.poll();
ends.add(iv[1]);
}
return ends.size();
}
/** Sweep line over half-open intervals; -1 sorts before +1 at ties. */
static int maxOverlap(int[][] intervals) {
int n = intervals.length;
int[][] events = new int[2 * n][];
for (int i = 0; i < n; i++) {
events[2 * i] = new int[]{intervals[i][0], +1};
events[2 * i + 1] = new int[]{intervals[i][1], -1};
}
Arrays.sort(events, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
int cur = 0, best = 0;
for (int[] ev : events) {
cur += ev[1];
best = Math.max(best, cur);
}
return best;
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
check(Arrays.deepEquals(mergeIntervals(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}, {17, 20}}),
new int[][]{{1, 6}, {8, 10}, {15, 20}}), "merge 1");
check(Arrays.deepEquals(mergeIntervals(new int[][]{{1, 4}, {4, 5}}), new int[][]{{1, 5}}), "merge touching");
check(Arrays.deepEquals(mergeIntervals(new int[][]{{1, 10}, {2, 3}}), new int[][]{{1, 10}}), "merge contained");
check(mergeIntervals(new int[0][]).length == 0, "merge empty");
check(Arrays.deepEquals(insertInterval(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5}),
new int[][]{{1, 5}, {6, 9}}), "insert 1");
check(Arrays.deepEquals(insertInterval(new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[]{4, 8}),
new int[][]{{1, 2}, {3, 10}, {12, 16}}), "insert 2");
check(Arrays.deepEquals(insertInterval(new int[0][], new int[]{5, 7}), new int[][]{{5, 7}}), "insert empty");
int[][][] roomInputs = {{{0, 30}, {5, 10}, {15, 20}}, {{0, 30}, {5, 10}, {15, 20}, {12, 25}},
{{7, 10}, {2, 4}}, {{1, 5}, {5, 10}}, {}};
int[] roomWant = {2, 3, 1, 1, 0};
for (int i = 0; i < roomInputs.length; i++) {
check(minMeetingRooms(roomInputs[i]) == roomWant[i], "rooms heap " + i);
check(maxOverlap(roomInputs[i]) == roomWant[i], "rooms sweep " + i);
}
System.out.println("ALL TESTS PASSED");
}
}
#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using Interval = std::pair<int, int>;
// Closed intervals; touching intervals merge. O(n log n).
std::vector<Interval> mergeIntervals(std::vector<Interval> a) {
std::sort(a.begin(), a.end());
std::vector<Interval> out;
for (const auto& [s, e] : a) {
if (!out.empty() && s <= out.back().second) out.back().second = std::max(out.back().second, e);
else out.push_back({s, e});
}
return out;
}
// intervals is sorted and disjoint. Three phases, O(n).
std::vector<Interval> insertInterval(const std::vector<Interval>& a, Interval nw) {
auto [s, e] = nw;
std::vector<Interval> out;
std::size_t i = 0, n = a.size();
while (i < n && a[i].second < s) out.push_back(a[i++]);
while (i < n && a[i].first <= e) {
s = std::min(s, a[i].first);
e = std::max(e, a[i].second);
++i;
}
out.push_back({s, e});
while (i < n) out.push_back(a[i++]);
return out;
}
// Half-open [s, e): a room is free at time e. Min-heap of end times.
int minMeetingRooms(std::vector<Interval> a) {
std::sort(a.begin(), a.end());
std::priority_queue<int, std::vector<int>, std::greater<int>> ends;
for (const auto& [s, e] : a) {
if (!ends.empty() && ends.top() <= s) ends.pop();
ends.push(e);
}
return static_cast<int>(ends.size());
}
// Sweep line over half-open intervals; -1 sorts before +1 at ties.
int maxOverlap(const std::vector<Interval>& a) {
std::vector<std::pair<int, int>> events;
events.reserve(2 * a.size());
for (const auto& [s, e] : a) {
events.push_back({s, +1});
events.push_back({e, -1});
}
std::sort(events.begin(), events.end());
int cur = 0, best = 0;
for (const auto& [t, delta] : events) {
cur += delta;
best = std::max(best, cur);
}
return best;
}
int main() {
assert((mergeIntervals({{1, 3}, {2, 6}, {8, 10}, {15, 18}, {17, 20}}) ==
std::vector<Interval>{{1, 6}, {8, 10}, {15, 20}}));
assert((mergeIntervals({{1, 4}, {4, 5}}) == std::vector<Interval>{{1, 5}}));
assert((mergeIntervals({{1, 10}, {2, 3}}) == std::vector<Interval>{{1, 10}}));
assert(mergeIntervals({}).empty());
assert((insertInterval({{1, 3}, {6, 9}}, {2, 5}) == std::vector<Interval>{{1, 5}, {6, 9}}));
assert((insertInterval({{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, {4, 8}) ==
std::vector<Interval>{{1, 2}, {3, 10}, {12, 16}}));
assert((insertInterval({}, {5, 7}) == std::vector<Interval>{{5, 7}}));
std::vector<std::pair<std::vector<Interval>, int>> roomTests = {
{{{0, 30}, {5, 10}, {15, 20}}, 2},
{{{0, 30}, {5, 10}, {15, 20}, {12, 25}}, 3},
{{{7, 10}, {2, 4}}, 1},
{{{1, 5}, {5, 10}}, 1},
{{}, 0}};
for (const auto& [data, want] : roomTests) {
assert(minMeetingRooms(data) == want);
assert(maxOverlap(data) == want);
}
std::cout << "ALL TESTS PASSED\n";
return 0;
}
type Interval = [number, number];
/** Closed intervals; touching intervals merge. O(n log n). */
function mergeIntervals(intervals: Interval[]): Interval[] {
const a = intervals.map((iv): Interval => [iv[0], iv[1]]).sort((x, y) => x[0] - y[0] || x[1] - y[1]);
const out: Interval[] = [];
for (const [s, e] of a) {
const last = out[out.length - 1];
if (last !== undefined && s <= last[1]) last[1] = Math.max(last[1], e);
else out.push([s, e]);
}
return out;
}
/** intervals is sorted and disjoint. Three phases, O(n). */
function insertInterval(intervals: Interval[], nw: Interval): Interval[] {
let [s, e] = nw;
const out: Interval[] = [];
let i = 0;
const n = intervals.length;
while (i < n && intervals[i][1] < s) out.push([intervals[i][0], intervals[i++][1]]);
while (i < n && intervals[i][0] <= e) {
s = Math.min(s, intervals[i][0]);
e = Math.max(e, intervals[i][1]);
i++;
}
out.push([s, e]);
while (i < n) out.push([intervals[i][0], intervals[i++][1]]);
return out;
}
/** Minimal binary min-heap of numbers (JS has no built-in). */
class MinHeap {
private a: number[] = [];
size(): number { return this.a.length; }
peek(): number { return this.a[0]; }
push(v: number): void {
this.a.push(v);
let i = this.a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p] <= this.a[i]) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]];
i = p;
}
}
pop(): number {
const top = this.a[0];
const last = this.a.pop() as number;
if (this.a.length > 0) {
this.a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < this.a.length && this.a[l] < this.a[m]) m = l;
if (r < this.a.length && this.a[r] < this.a[m]) m = r;
if (m === i) break;
[this.a[m], this.a[i]] = [this.a[i], this.a[m]];
i = m;
}
}
return top;
}
}
/** Half-open [s, e): a room is free at time e. Min-heap of end times. */
function minMeetingRooms(intervals: Interval[]): number {
const a = [...intervals].sort((x, y) => x[0] - y[0]);
const ends = new MinHeap();
for (const [s, e] of a) {
if (ends.size() > 0 && ends.peek() <= s) ends.pop();
ends.push(e);
}
return ends.size();
}
/** Sweep line over half-open intervals; -1 sorts before +1 at ties. */
function maxOverlap(intervals: Interval[]): number {
const events: [number, number][] = [];
for (const [s, e] of intervals) {
events.push([s, 1]);
events.push([e, -1]);
}
events.sort((x, y) => x[0] - y[0] || x[1] - y[1]);
let cur = 0, best = 0;
for (const [, delta] of events) {
cur += delta;
best = Math.max(best, cur);
}
return best;
}
function assertEq(actual: unknown, expected: unknown, what: string): void {
const a = JSON.stringify(actual), b = JSON.stringify(expected);
if (a !== b) throw new Error(`${what}: got ${a}, want ${b}`);
}
assertEq(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18], [17, 20]]), [[1, 6], [8, 10], [15, 20]], "merge 1");
assertEq(mergeIntervals([[1, 4], [4, 5]]), [[1, 5]], "merge touching");
assertEq(mergeIntervals([[1, 10], [2, 3]]), [[1, 10]], "merge contained");
assertEq(mergeIntervals([]), [], "merge empty");
assertEq(insertInterval([[1, 3], [6, 9]], [2, 5]), [[1, 5], [6, 9]], "insert 1");
assertEq(insertInterval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]), [[1, 2], [3, 10], [12, 16]], "insert 2");
assertEq(insertInterval([], [5, 7]), [[5, 7]], "insert empty");
const roomTests: [Interval[], number][] = [
[[[0, 30], [5, 10], [15, 20]], 2],
[[[0, 30], [5, 10], [15, 20], [12, 25]], 3],
[[[7, 10], [2, 4]], 1],
[[[1, 5], [5, 10]], 1],
[[], 0],
];
for (const [data, want] of roomTests) {
assertEq(minMeetingRooms(data), want, "rooms heap");
assertEq(maxOverlap(data), want, "rooms sweep");
}
console.log("ALL TESTS PASSED");
Variants worth having in your fingers
Activity selection in six lines (Python). Sort by end; keep the last chosen end.
def max_disjoint(intervals: list[list[int]]) -> int:
count, last_end = 0, float("-inf")
for s, e in sorted(intervals, key=lambda iv: iv[1]):
if s >= last_end: # half-open: touching is fine
count += 1
last_end = e
return count
assert max_disjoint([[1, 3], [2, 4], [3, 5]]) == 2
assert max_disjoint([[1, 2], [2, 3], [3, 4], [1, 3]]) == 3
assert max_disjoint([]) == 0
print("ok")
Skyline with a lazy-deletion max-heap. See the solution to LeetCode 218 in the Practice ladder.
Difference array for weighted overlap (car pooling). See the Prefix Sums page; the shape is diff[s] += w; diff[e] -= w, prefix-sum, check the maximum.
Real-world uses
Calendar systems and free/busy. Google Calendar's and Exchange's free/busy lookups take each attendee's busy intervals, flatten and merge them, and present the gaps — Employee Free Time at scale. The iCalendar standard (RFC 5545) represents busy time as FREEBUSY periods that are half-open start/end ranges, and the "find a meeting time" feature is interval partitioning over rooms plus activity selection over people's constraints.
OS CPU scheduling and reservations. Real-time schedulers such as Earliest Deadline First are the earliest-end greedy applied to jobs with deadlines; admission control for a reservation-based scheduler checks whether adding a new reservation would push the depth of overlapping reservations above the number of cores — Meeting Rooms II with cores as rooms. See CPU Scheduling.
Register allocation by linear scan. A compiler computes the live interval of each variable (first definition to last use, as instruction indices), sorts by start, and sweeps: at each interval start it expires every active interval that has ended (freeing a register), then assigns a free register or spills. This is interval partitioning with a fixed number of rooms, and when the demand exceeds the registers it spills the interval that ends furthest in the future. Poletto & Sarkar, "Linear Scan Register Allocation", ACM TOPLAS 21(5), 1999, introduced it as a fast alternative to graph colouring; variants run in V8, HotSpot's C1 and LLVM's fast allocator.
Memory allocator coalescing. A free list stores free byte ranges. When a block is freed, the allocator checks whether the range immediately before or after it is also free and merges them — this is "merge intervals" where touching ranges must merge (adjacent free blocks must become one), the opposite tie-break from meeting rooms. Boundary tags make the neighbour lookup . See Memory Allocators.
Database range locks and MVCC windows. A lock manager that supports range locks (key-range locking in SQL Server, gap and next-key locks in InnoDB) must answer "does this requested range overlap any held range?" — an interval-tree or ordered-map query per request. In MVCC, every row version is visible for a window of transaction IDs , and visibility checking is the point-in-interval test against a snapshot. See MVCC.
Time-range queries in time-series stores. TimescaleDB chunks, InfluxDB shards and Prometheus blocks each cover a time interval. A query over first prunes to the chunks whose interval overlaps the query — the overlap test applied to metadata — before touching any data. See Time-Series Storage Engines.
LSM-tree compaction. In levelled compaction (RocksDB, LevelDB), each SSTable in level covers a disjoint key range. To compact a file from level , the engine finds every file in level whose key range overlaps it — an overlap query over sorted ranges, done by binary search — and merges exactly those. Choosing the file with the fewest overlaps is the standard write-amplification heuristic. See Storage Engines.
Genomics. A genome annotation is a set of intervals on each chromosome. bedtools intersect (Quinlan & Hall, Bioinformatics 2010) reports overlaps between two BED files — "interval list intersections" over millions of records — using sorted sweeps or interval trees; BED coordinates are half-open and 0-based, which is the canonical example of why you must read the convention before you compare endpoints.
Pitfalls & edge cases
- Closed vs half-open, and touching intervals.
[1,5]and[5,8]overlap when closed, not when half-open. The difference is<=vs<in the heap check, the sweep tie-break, and the merge test. Decide first; then write the comparison; then test the touching case explicitly. - Sorting by end when you meant start, or vice versa. Merge, insert, meeting rooms and sweep need start order. Activity selection and minimum arrows need end order. Sorting activity selection by start is the classic wrong greedy (a long early interval blocks many short ones).
- Mutating while merging. Appending
[s, e]as a reference to the input and then extendingout[-1][1]mutates the caller's data (Python lists, Java arrays, JS arrays are all references). Copy before you extend. - Heap of ends when a new start equals an end. With half-open intervals the room is free: use
heap.top() <= start. Writing<costs one extra room and fails[[1,5],[5,10]]. - Assuming the input is sorted. Merge Intervals (56) is unsorted; Insert Interval (57) is sorted and disjoint, which is what makes the three-phase pass valid. Re-sorting in 57 is correct but wastes the guarantee.
- The
maxin extend.cur.end = next.endfails for contained intervals ([1,10]then[2,3]). - Empty input and single interval. Most bugs in merge come from
out[-1]on an empty list. Guard, or use the "if out and …" shape. - 32-bit timestamps and overflow. Unix seconds overflow signed 32-bit in 2038; milliseconds already exceed 32 bits; Java
intarithmetic onend - startof millisecond timestamps silently wraps. Use 64-bit (long,int64_t, Python int, JSnumberup to orBigInt). - Zero-length intervals.
[5,5]is a point when closed and empty when half-open. Decide whether the problem allows them; the overlap test handles both correctly only if you kept the convention consistent. - Duplicates. Identical intervals are fine for merge and rooms (two identical meetings need two rooms — the sweep and heap both get it right), but activity selection must not count both.
- Negative coordinates and
float("-inf")sentinels. Use a true sentinel rather than-1for "no previous end" when coordinates can be negative.
Variations
- Circular intervals / time wraparound. Shifts on a 24-hour clock that cross midnight (
[22, 2)) break the total order. Either split each wrapping interval into two ([22, 24)and[0, 2)) and solve on the line, or "unroll" by duplicating every interval shifted by the period and solving on with care to count each original once. - 2D rectangles. Area of union, or maximum overlap of rectangles: sweep in with the active set being a set of -intervals, which itself needs a segment tree with coverage counts to answer "total covered -length" in . Named here only; Module 3 builds the segment tree.
- Weighted intervals. Weighted interval scheduling (DP, Module 6); weighted depth (car pooling, bandwidth) via weighted sweep or difference array.
- -overlap queries. "Which points are covered by at least intervals?" — the sweep with running count, emitting stretches where count . "Does a point exist covered by ?" is Calendar III's question.
- Online insertion with a balanced tree. When intervals arrive one at a time and each insertion must return the merged state (LeetCode 352, 715), keep disjoint intervals in an ordered map keyed by start; insertion finds the neighbours by
floor/ceilingand merges locally. per operation amortised.
Practice ladder
Each entry: what it is in my words, what it teaches, a hint. Four have full solutions.
1. Merge Intervals (LeetCode 56) — unsorted closed intervals; return the merged disjoint list. Teaches the master move and the max in extend.
Hint
Sort by start. Compare each interval's start with the last output interval's end, not with the previous input interval.
2. Insert Interval (LeetCode 57) — sorted disjoint list plus one new interval. Teaches the three-phase pass and respecting an input guarantee.
Hint
Three while loops with the same index. Phase 1 condition: end < new.start. Phase 2 condition: start <= new.end.
3. Meeting Rooms (LeetCode 252, premium) — can one person attend every meeting? Teaches the sorted adjacent-pair check.
Hint
After sorting by start, a conflict can only be between consecutive meetings. Why? Use the master-move claim.
4. Meeting Rooms II (LeetCode 253, premium) — minimum rooms. Teaches the heap of ends and the sweep, and the <= tie-break. Also available as CSES Restaurant Customers, below.
Hint
Write the sweep first (it is shorter), then the heap, and make them agree on [[1,5],[5,10]].
5. Non-overlapping Intervals (LeetCode 435) — fewest removals so that the rest are pairwise non-overlapping (touching allowed). Teaches activity selection as a complement.
Hint
Answer = (maximum number of disjoint intervals). Sort by end.
Solution
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
intervals.sort(key=lambda iv: iv[1]) # earliest end first
removed, last_end = 0, float("-inf")
for s, e in intervals:
if s >= last_end: # touching is allowed here
last_end = e # keep it
else:
removed += 1 # it overlaps the kept one: drop it
return removed
assert erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]) == 1
assert erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]) == 2
assert erase_overlap_intervals([[1, 2], [2, 3]]) == 0
print("ok")
time, extra space. Correct by the exchange argument: keeping the earliest-ending interval never hurts.
6. Interval List Intersections (LeetCode 986) — two sorted disjoint lists; return every pairwise intersection. Teaches two pointers on intervals and "advance the one that ends first".
Hint
Intersection is [max(starts), min(ends)], valid when max(starts) <= min(ends). After emitting, advance the pointer of the interval with the smaller end.
Solution
def interval_intersection(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
i = j = 0
out: list[list[int]] = []
while i < len(a) and j < len(b):
lo = max(a[i][0], b[j][0])
hi = min(a[i][1], b[j][1])
if lo <= hi: # closed intervals: a shared point counts
out.append([lo, hi])
if a[i][1] < b[j][1]: # the one that ends first can't meet anything else
i += 1
else:
j += 1
return out
assert interval_intersection([[0, 2], [5, 10], [13, 23], [24, 25]],
[[1, 5], [8, 12], [15, 24], [25, 26]]) == \
[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]
assert interval_intersection([[1, 3], [5, 9]], []) == []
print("ok")
time, extra space.
7. Minimum Number of Arrows to Burst Balloons (LeetCode 452) — closed intervals; fewest vertical arrows stabbing all. Teaches the stabbing dual of activity selection and the closed-interval <=.
Hint
Sort by end. Shoot at the first balloon's end; every balloon whose start is <= that position is already burst.
Solution
def find_min_arrow_shots(points: list[list[int]]) -> int:
if not points:
return 0
points.sort(key=lambda p: p[1])
arrows, shot_at = 1, points[0][1]
for s, e in points[1:]:
if s > shot_at: # closed intervals: s == shot_at is still burst
arrows += 1
shot_at = e
return arrows
assert find_min_arrow_shots([[10, 16], [2, 8], [1, 6], [7, 12]]) == 2
assert find_min_arrow_shots([[1, 2], [3, 4], [5, 6], [7, 8]]) == 4
assert find_min_arrow_shots([[1, 2], [2, 3], [3, 4], [4, 5]]) == 2
print("ok")
time. The number of arrows equals the maximum number of pairwise-disjoint balloons.
8. Car Pooling (LeetCode 1094) — trips with passenger counts and pickup/drop-off stops in ; can capacity ever be exceeded? Teaches the weighted sweep as a difference array.
Hint
diff[from] += p; diff[to] -= p, prefix-sum, check every value is <= capacity. Drop-offs happen before pickups at the same stop — which tie-break is that?
9. Employee Free Time (LeetCode 759, premium) — several sorted schedules; the common free intervals. Teaches merge-then-gaps and the -way-merge alternative.
Hint
Flatten, sort, merge. Each gap between consecutive merged intervals is free for everyone.
10. Remove Covered Intervals (LeetCode 1288) — count intervals not fully contained in another. Teaches a sort with a secondary key.
Hint
Sort by start ascending, and by end descending for equal starts. Then an interval is covered iff its end is <= the maximum end seen so far.
11. My Calendar I, II, III (LeetCode 729, 731, 732) — online booking with no double / no triple booking / report the max booking depth. Teaches the progression from a list scan to two lists to a difference map.
Hint
III: an ordered map time → delta. After each booking, sweep the map's keys in order and track the maximum running sum.
Solution (My Calendar III)
class MyCalendarThree:
def __init__(self) -> None:
self.diff: dict[int, int] = {}
def book(self, start: int, end: int) -> int: # half-open [start, end)
self.diff[start] = self.diff.get(start, 0) + 1
self.diff[end] = self.diff.get(end, 0) - 1
cur = best = 0
for t in sorted(self.diff): # ends at t subtract before starts at t add
cur += self.diff[t]
best = max(best, cur)
return best
cal = MyCalendarThree()
assert [cal.book(10, 20), cal.book(50, 60), cal.book(10, 40),
cal.book(5, 15), cal.book(5, 10), cal.book(25, 55)] == [1, 1, 2, 3, 3, 3]
print("ok")
per booking here because of the sorted (an ordered map makes it per booking); total for bookings. Because starts and ends at the same time are summed into one delta before the sweep reads it, the half-open tie-break is automatic.
12. The Skyline Problem (LeetCode 218) — buildings as [left, right, height]; output the key points of the upper envelope. Teaches the general sweep with a max-heap and lazy deletion.
Hint
Events: (left, -height, right) for starts and (right, 0, 0) for ends, so starts sort before ends at the same x and taller starts come first. Heap of (-height, right); before reading the top, pop everything whose right <= x.
Solution
import heapq
def get_skyline(buildings: list[list[int]]) -> list[list[int]]:
events: list[tuple[int, int, int]] = []
for left, right, h in buildings:
events.append((left, -h, right)) # start: taller first at equal x
events.append((right, 0, 0)) # end
events.sort()
heap: list[tuple[int, float]] = [(0, float("inf"))] # (-height, right); ground never expires
out: list[list[int]] = []
for x, neg_h, right in events:
while heap[0][1] <= x: # lazy deletion of buildings that have ended
heapq.heappop(heap)
if neg_h:
heapq.heappush(heap, (neg_h, right))
height = -heap[0][0]
if not out or out[-1][1] != height:
out.append([x, height])
return out
assert get_skyline([[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]) == \
[[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
assert get_skyline([[0, 2, 3], [2, 5, 3]]) == [[0, 3], [5, 0]]
print("ok")
time: each building is pushed and popped at most once. The sentinel (0, inf) makes the heap never empty, so the height drops to 0 naturally when the last building ends.
13. Data Stream as Disjoint Intervals (LeetCode 352) and Range Module (LeetCode 715) — online insertion (and removal) into a set of disjoint intervals. Teaches the ordered-map-of-intervals structure.
Hint
Keep intervals in a sorted structure keyed by start. On insert, find the predecessor and successor, merge if they touch, replace. For Range Module remove, re-insert the up-to-two leftover pieces.
14. Maximum Number of Events That Can Be Attended (LeetCode 1353) and Meeting Rooms III (LeetCode 2402) — attend one event per day choosing wisely; or route meetings to the lowest-numbered free room, delaying when none is free. Teaches sweeping over days with a heap of deadlines, and two heaps (free rooms, busy rooms by end time).
Hint
1353: sweep day by day; push events that have started, pop expired ones, attend the one with the earliest deadline. 2402: a min-heap of free room indices and a min-heap of (end, room); when a meeting is delayed its duration is preserved.
15. CSES Movie Festival (1629), Movie Festival II (1632), Restaurant Customers (1619), Room Allocation (1164) — activity selection; activity selection with people (a multiset of each person's last end, always reuse the one ending latest that still fits); maximum concurrent customers (sweep); and Meeting Rooms II that must also print the room assignment (heap of (end, room)). Teaches the same four moves under contest input sizes (), where fails.
Hint
Movie Festival II: for each movie in end order, find the person whose current end is the largest value <= the movie's start (std::multiset::upper_bound then step back); if none, nobody can watch it. Room Allocation: the heap pop gives you the room number to reuse.
Common mistakes & interview follow-ups
"What if the intervals arrive as a stream?" For merge: keep an ordered map of disjoint intervals and merge locally on each arrival (LeetCode 352) — per insert. For depth: a difference map re-swept each time is per insert; a dynamic segment tree over compressed coordinates (or a Fenwick tree if all coordinates are known upfront) gives .
"What if memory is limited and the data is on disk?" External sort by start (merge sort on disk), then the merge pass is a sequential stream with state — merge intervals is a streaming algorithm once sorted. The sweep needs the events sorted too but then is also state.
"What if there are resources and you want to maximise the number of intervals served?" Movie Festival II: sort by end, and for each interval assign it to the resource whose last end is the largest value its start. A multiset (balanced tree) makes this . Picking the earliest-free resource instead is a common wrong greedy.
"Why does sorting by start fail for activity selection?" Counter-example: [1,100], [2,3], [4,5]. Earliest start picks the long one and gets 1; earliest end gets 2.
"Can you do Meeting Rooms II in ?" Only when coordinates are small integers (difference array, ). In the comparison model the sort is a lower bound.
"How would you return which room each meeting uses?" Heap of (end, room_id); on reuse pop and push with the same room_id; on a new room assign the next id. CSES Room Allocation is exactly this.
"What changes with closed intervals?" Flip the tie-break: +1 before −1 in the sweep, heap.top() < start in the heap, s <= cur.end stays for merge (touching merges in both conventions for merge, since [1,5] and [5,8] share a point when closed; for half-open merge you may choose to merge touching intervals to keep the union canonical).
"Weighted version?" Not greedy. DP over end-sorted intervals with binary search for the predecessor, .
Quick quiz
- Two half-open intervals
[3, 7)and[7, 12): do they overlap? What about closed[3, 7]and[7, 12]?
Answer
Half-open: no — 7 belongs only to the second. Closed: yes — they share the point 7. The test is a.start < b.end && b.start < a.end (half-open) versus <= (closed).
- After sorting by start, why is it enough to compare the next interval with only the current merged block and not with every earlier block?
Answer
Every earlier emitted block ended strictly before the current block started, and the next interval starts at or after the current block's start. So the next interval starts strictly after every earlier block's end and cannot overlap any of them.
- In the sweep for Meeting Rooms II with half-open intervals, events at equal times are ordered so that −1 comes before +1. What goes wrong if you reverse that?
Answer
A meeting ending at and one starting at are counted as simultaneous; the running count momentarily exceeds the true depth. [[1,5],[5,10]] would report 2 rooms instead of 1.
- The minimum number of rooms equals the maximum depth of overlap. Which direction is the "easy" inequality, and what argument gives the other?
Answer
Rooms depth is easy (pigeonhole at the deepest point). Rooms depth follows from the greedy: when it opens room , the occupied rooms hold meetings that started no later than and end after the current start, so the depth at that start is at least .
- Why does the earliest-start greedy fail for activity selection, and what sort key fixes it?
Answer
An early, long interval blocks many short later ones ([1,100] vs [2,3],[4,5]). Sort by earliest end: the chosen interval then constrains the future as little as possible, and the exchange argument proves optimality.
Further reading / sources
- Kleinberg & Tardos, Algorithm Design, §4.1 "Interval Scheduling" and "Interval Partitioning" (the depth proof), §6.1 "Weighted Interval Scheduling".
- CLRS, Introduction to Algorithms, §16.1 "An activity-selection problem" (exchange argument), §14.3 "Interval trees".
- de Berg, Cheong, van Kreveld, Overmars, Computational Geometry: Algorithms and Applications, chapter 2 (the sweep-line paradigm).
- M. Poletto & V. Sarkar, "Linear Scan Register Allocation", ACM Transactions on Programming Languages and Systems 21(5), 1999. doi:10.1145/330249.330250
- A. R. Quinlan & I. M. Hall, "BEDTools: a flexible suite of utilities for comparing genomic features", Bioinformatics 26(6), 2010.
- Wikipedia: Interval scheduling, Sweep line algorithm, Interval graph.
- Archon: Greedy Algorithms (activity selection, interval partitioning, weighted scheduling), Heaps & Priority Queues, Sorting & Searching, Advanced Data Structures, Spatial Indexing.
Module 1 navigation. Previous: Monotonic Stack & Monotonic Deque. Next: Linked Lists. Module overview: Linear Data Structures. Related in this module: Two Pointers, Prefix Sums & Difference Arrays, Sliding Window, Hash Tables. Course home: DSA: Zero to Mastery.