The idea: every meeting happens, in as few rooms as possible

You have a list of meetings, each with a start and a finish time, and every meeting must happen. Two meetings that overlap can't share a room. What is the smallest number of rooms that is enough? This is interval partitioning, also called the meeting rooms problem or interval colouring. A meeting is written [s, f): it runs from s up to f, so one room can host [0, 2) and then [2, 5).

Nine meetings A to I on a time line from 0 to 18, packed into three rooms. Room 1 holds A, C, H and I; room 2 holds B, E and F; room 3 holds D and G. A dashed line at t = 4 crosses B, C and D, one in each room.
The page's 9 meetings fit in 3 rooms, and 3 is the least possible: at t = 4, B, C and D all run.

The depth: a lower bound

The depth of a set of meetings is the largest number of them that run at the same moment. If d meetings all run at time t, each of them needs its own room at t, so every schedule uses at least d rooms. This bound says nothing about any algorithm; it is a fact about the meetings.

To find the depth, move a sweep line along the time line and count the meetings with s ≤ t < f. On the page's meetings the count is at most 3, first at t = 4, where B [0, 5), C [3, 9) and D [4, 8) overlap. (Demo: depth sweep) A real program sorts the 2n start and end points and adds 1 at a start, subtracts 1 at an end.

The depth row for the 9 meetings: one cell per unit of time from 0 to 17 with the number of meetings running. The counts are 2 2 1 2 3 3 3 3 2 2 3 3 1 1 1 1 1 0; the cells with 3 are darkest. A sweep line at t = 4 crosses B, C and D.
The depth row counts meetings running at each time; its maximum, 3, is the fewest rooms any schedule can use.

The greedy: by start time, into the room free earliest

  1. Sort the meetings by start time.
  2. Keep each open room with the time it is free at (the finish of its last meeting), in a min-heap keyed by that time.
  3. For each meeting, look at the room that is free earliest. If it is free by the meeting's start, put the meeting there. Otherwise every room is busy: open a new room.

On the page: A takes room 1, B overlaps A and opens room 2, C starts at 3 when room 1 is free (at 2), so C takes room 1. D starts at 4: room 1 is busy until 9 and room 2 until 5, so room 3 opens. After that no new room is needed: E takes room 2, F room 2, G room 3, H room 1, I room 1. Three rooms. (Demo: greedy by start time) Sorting takes O(n log n) and each heap step O(log n).

Why greedy meets the bound

Suppose greedy opens room k + 1 for a meeting j that starts at s. It does that only because all k rooms are busy at s. Each room's last meeting started no later than s (meetings come in start order) and ends after s. So those k meetings and j all run at time s: the depth is at least k + 1. So greedy never uses more rooms than the depth, and no schedule can use fewer. Greedy is optimal. On the page, room 3 opens for D at t = 4, exactly where the sweep finds B, C, D.

The proof only needs "use any free room". Taking the room that is free earliest is just how a heap finds a free one quickly.

The wrong order: by finish time

Sorting by finish time is the right greedy for interval scheduling (one room, as many meetings as possible), but here it fails, even with first fit (the lowest room that has no overlap). Meetings get placed out of time order, so a room can be filled at both ends and the gap in between is too small. On the same 9 meetings, room 1 gets A, E, then G; when F [7, 13) comes it overlaps G in room 1, H in room 2, D in room 3 and C in room 4, and a fifth room opens. (Demo: by finish time fails)

Left: by start time, three rooms, marked correct. Right: by finish time with first fit, five rooms: room 1 holds A, E, G, I; room 2 B, H; room 3 D; room 4 C; room 5 F. Marked wrong.
Same meetings, two orders: by start time needs 3 rooms, by finish time first fit needs 5.

The demos in numbers

orderroom rulerooms on the 9 meetingsdepth
start timeroom free earliest✓ 33
finish timefirst fit✗ 53

Press Random Set for new meetings: by start time always uses exactly the depth, by finish time sometimes more. (Demo: random set)

Interval partitioning is graph colouring on an interval graph (one node per meeting, an edge for each overlap): for interval graphs the fewest colours equals the largest clique, which is the depth. The same idea assigns registers to variables whose live ranges are intervals, and CPUs or gates to jobs. See also Interval Scheduling for the one-room version, Huffman Coding for another greedy with a proof, and CPU Scheduling for jobs over time on one CPU.

For jobs that may run in any order on one machine, see Minimize Lateness, proved optimal by an exchange argument.

What the page leaves out

Times are whole numbers from 0 to 18 and a set has at most 10 meetings. The page leaves out the online version (meetings arrive one at a time and must be placed at once), weighted rooms, meetings that may move in time, and general graph colouring, where no greedy order is always optimal.