Given a set of talks, each with a start and end time, how many rooms does a conference need to run every single one of them, with no two talks ever sharing a room at overlapping times? This is interval partitioning (also called minimum meeting rooms): a third distinct question over the same kind of interval input the site's other Greedy entries already answer. Activity Selection picks the largest non-conflicting subset for one resource, discarding the rest. Interval Point Cover finds the fewest points that touch every interval. This page drops everyone instead — every talk runs, on schedule, in full — and asks only how many parallel resources that takes.
The greedy idea: sort every interval by start time, then walk the list once. For each interval, check whether any currently open room's most recent talk has already ended by this one's start time. If one has, reuse whichever such room frees soonest. If none has, open a new room. This is the site's eighth entry filed under Greedy, and unlike the other seven, its proof isn't an exchange argument at all — see Why it works below.
Type a list of start-end talks (comma-separated), pick a room-assignment rule, and
press Load, then Step or Run. Rooms appear as
new rows only when a talk actually needs one. A green bar means the talk reused an existing room;
a soft-tan bar means it forced a brand new room open; a red dashed bar means the demo's own
independent check — which re-examines every pair of talks ever placed in the same room, not just
the algorithm's own bookkeeping — found a real double-booking.
rooms
Five of the site's other nine Greedy entries — Huffman
Coding, Activity Selection,
Fractional Knapsack,
Job Sequencing, and
Interval Point Cover — prove optimality with an
exchange argument — take an optimal solution that disagrees with greedy, swap greedy's choice in,
show nothing gets worse. (The remaining three take different shapes entirely:
Coin Change is only exact for the right denominations,
Set Cover trades exactness for a provable ratio bound, and
Greedy Coloring doesn't even get that.) Interval
Partitioning doesn't need an exchange argument either, because there's a bound that pins the
answer down from both directions at once. Let D be the largest number of talks
active at any single instant (the maximum "depth" of overlap). Lower bound: those
D talks all overlap each other at that instant, so no two of them can share a room —
any valid schedule needs at least D rooms, full stop, independent of any algorithm.
Upper bound: processing talks in start order, the greedy rule only ever opens a
(k+1)-th room for a talk when all k existing rooms are simultaneously
still busy at that talk's start time — meaning k+1 talks (the new one plus one per
busy room) are genuinely active together right then, so D ≥ k+1. Greedy can
therefore never open more than D rooms. Since no schedule can use fewer than
D and greedy never uses more, greedy hits D exactly, on every input.
Which specific free room gets reused doesn't affect this count at all — "reuse the one that frees
soonest" is just the standard, heap-friendly way to always find a free room fast, not a
requirement of the proof.
On the demo's own eight-talk default set, this rule opens exactly 3 rooms. Talk 1
spans the whole conference (0–30), so it alone accounts for one room throughout
— but between times 6 and 10, talks 1, 2, and 7 are all in progress at
once, the deepest overlap anywhere in the set, which is exactly why a third room is unavoidable
(and, separately, why a fourth never is). The two rules below don't reach 3 on the same
data — see Pitfalls.
A real implementation keeps open rooms in a small binary min-heap, keyed by when each one next
frees, so "find the room that frees soonest" and "update it" are both O(log n)
instead of a linear scan:
function intervalPartitioning(talks) {
const sorted = [...talks].sort((a, b) => a.start - b.start);
// Binary min-heap of open rooms, keyed by room.end.
const heap = [];
const swap = (i, j) => { [heap[i], heap[j]] = [heap[j], heap[i]]; };
const siftUp = (i) => {
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p].end <= heap[i].end) break;
swap(p, i); i = p;
}
};
const siftDown = (i) => {
const n = heap.length;
for (;;) {
let s = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && heap[l].end < heap[s].end) s = l;
if (r < n && heap[r].end < heap[s].end) s = r;
if (s === i) break;
swap(s, i); i = s;
}
};
let roomCount = 0;
const assignment = [];
for (const talk of sorted) {
if (heap.length && heap[0].end <= talk.start) {
heap[0].end = talk.end; // reuse the soonest-freeing room
siftDown(0);
assignment.push({ ...talk, room: heap[0].id });
} else {
const room = { id: roomCount++, end: talk.end };
heap.push(room);
siftUp(heap.length - 1); // open a new room
assignment.push({ ...talk, room: room.id });
}
}
return { roomsNeeded: roomCount, assignment };
}Only checking the most recently used room, instead of scanning every open room, wastes
rooms — but never double-books one. Switch the demo's rule to only check the most
recently used room on the unchanged default data: every talk still lands in a genuinely free
room (this variant never produces an invalid schedule), but it opens 6 rooms
instead of 3. The failure mode is concrete on this exact data: talk 0–5 opens
room 1 and immediately finishes. Room 1 then sits free for the rest of the conference, but because
every later talk only ever checks whichever room was used last — not room 1 specifically —
it never gets reconsidered, and the demo keeps opening brand new rooms instead. Checked beyond this
one example: across 20,000 randomized trials (2–11 talks each, times 0–19), this
variant opened more rooms than the true minimum in 14,002 of them (70%), confirmed against an
independently computed maximum-overlap depth, never merely close.
Comparing a candidate room's free time against the new talk's end, instead of its
start, produces an actively double-booked schedule. Switch the demo's rule to reuse
if the room frees before this talk ends on the unchanged default data: the very second talk
processed, 0–30, gets placed in the same room as the first, 0–5,
because 5 ≤ 30 reads as "free enough" under this rule — even though the new talk
starts at 0, before the room's occupant has even begun to leave. The demo's own
end-of-run check, which independently re-examines every pair of talks sharing a room for actual
time overlap rather than trusting the assignment loop's own bookkeeping, flags both talks red. This
is an easy field mix-up to make by hand — "is the room free for this talk" sounds like it should
compare against something about the talk, and a candidate's own end field is sitting right
there — but the room only being free at the talk's end makes it free for what comes
after this talk, not for the talk itself, which needs the room free already
at its start. Checked beyond the hand-traced example: across the same 20,000-trial
sweep, this variant produced at least one genuine double-booking in 17,020 of them (85%).
Time: O(n log n) — the initial sort, plus one
O(log n) heap operation per talk (a possible pop-and-repush to update the
soonest-freeing room's key, or a single push to open a new one). Space:
O(n) for the sorted copy, the heap, and the returned room assignment. The two buggy
rules above are no cheaper — the difference is entirely in which room gets picked, not how many
comparisons it costs.
See Choosing a Greedy Strategy for how this entry's proof compares against the site's other nine Greedy entries — short version: this is the guide's first entry that's exact by matching a lower bound to an upper bound instead of by exchange argument, though it's no less airtight for it.