Greedy scheduling with a heap

46 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Three meetings: [0, 30], [5, 10], [15, 20]. How many rooms are needed so that none overlap? By hand you draw them on a time line and count the thickest overlap: at time 7, two meetings are running, so two rooms. The drawing method works for three meetings. For ten thousand, you would need to compare every pair, about 50 million pairs, or walk the time line minute by minute, which is slow if times are large.

A simpler mental picture: people arrive at a building in order of start time. Each one asks "is any room free right now?" A room is free if the meeting in it ended before this one starts. To answer, we only need to know the earliest ending time among the meetings currently running.

Build the structure, one piece at a time

Piece one: sort the meetings by start time, so we handle arrivals in order. That is the queue at the door.

Piece two: a min-heap of end times, one entry per occupied room. Its top is the room that frees up soonest.

Piece three: the loop. For each meeting in start order, look at the heap top. If that end time is at most the meeting's start, the room is free: pop it (the old meeting is over). Then push the new meeting's end time. The number of entries in the heap after the push is the number of rooms in use right now; the answer is the largest size the heap ever reaches.

Maximum rooms in use: 2.

Why it is correct

The invariant: just before a meeting with start s is handled, the heap holds the end times of exactly the meetings that started earlier and are still running at time s, except possibly one that has just ended and is about to be popped. Popping only the top is enough because if the earliest end is still after s, every other end is too, so no room is free.

rooms needed = max over time t of (number of meetings with start ≤ t < end) = max heap size

Why is reusing a free room never a mistake? Rooms are interchangeable; what matters is only how many are busy at each moment, and that count is fixed by the meetings, not by which room each one uses. The heap size tracks that count exactly at each start time, and the count can only increase at a start time, so checking at start times finds the maximum.

Why it is fast

Sorting costs O(n log n). Each meeting then does at most one pop and one push on a heap of at most n entries: O(n log n) total. For ten thousand meetings that is a few hundred thousand steps, against 50 million pair comparisons.

How to recognise it in an interview

"Minimum number of rooms / machines / servers", "assign each job to the first available worker", "process tasks in order of start time with the shortest first", "which room hosts the most meetings". Say: "Sort by start, keep a min-heap of end times; the heap top tells me the earliest resource to free up." Meeting Rooms II is this exactly. Meeting Rooms III adds a second heap of free room numbers so that the lowest-numbered free room is chosen. Single-Threaded CPU sorts tasks by arrival and keeps a heap ordered by processing time for the tasks that have already arrived.

02The idea in one line

Sort by start; a heap of end times tells you the earliest room that frees up.

Reach for it when: Meeting rooms II/III, task scheduler, CPU scheduling, reorganise string.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: Meeting Rooms II on [[0,30],[5,10],[15,20]]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort by start; the heap holds the end time of every running meeting
2. Meeting [0,30] arrives; earliest-ending running meeting ends at —
3. No room free yet: open room 1
4. Push its end 30; the heap size is the number of rooms in use
5. Meeting [5,10] arrives; earliest-ending running meeting ends at 30
6. No room free yet: open room 2
7. Push its end 10; the heap size is the number of rooms in use
8. Meeting [15,20] arrives; earliest-ending running meeting ends at 10
9. 10 ≤ 15: that room is free, reuse it
10. Push its end 20; the heap size is the number of rooms in use
11. Rooms needed = max heap size = 2
12. Sort plus one heap op per meeting: O(n log n)

04Asked at Google

10 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Heap: Top-k with a size-k heap, Two heaps (running median), K-way merge, Lazy deletion heap, Pop-k-then-rebuild (frequency greedy).