Scheduling with heaps

Run a timeline event by event. One heap says which room frees up next; another picks which free room or job goes now.

what

Sort arrivals by time and jump the clock from event to event. A min-heap of busy-until times says what finishes next; a second heap picks among the free rooms or ready jobs.

use when

Meetings, jobs or requests arrive over time and each needs one of several rooms, servers or CPUs, or timed events must fire in order.

time

O(n log n)

space

O(n)

You’ll recognise it when

Things arrive over time, and each one needs one of several rooms, servers, machines or workers.
You must know which one it gets: the lowest-numbered free room, or the server that frees up first.
The question asks how many rooms or machines you need so that nobody waits.
One worker always picks the most urgent job that has arrived: the shortest, the highest priority, or the earliest deadline.
Events are due at future times (retries, expiries, timers), and times go up to 10⁹, so ticking the clock one unit at a time is far too slow.

If you only need a count, the interval sweep over sorted starts and ends is enough. Heaps earn their place when you must know which room, or when running a job changes what happens next.

Picture a receptionist who hands out meeting rooms. She doesn’t walk the corridor to check every door. On her desk she keeps a board of busy rooms, sorted by when each one empties, and a tray of keys for free rooms, lowest number first. When a guest arrives at 10:00, she looks at the top of the board. If that room is empty by 10:00, its key goes back in the tray, and she looks at the board again. Then she hands over the lowest key in the tray, or opens a new room if the tray is empty.

Two ideas make this fast. First, time jumps from event to event. Nothing changes between one arrival and the next, so you never tick a clock. Second, at each event you only need the smallest item somewhere: the earliest end, the lowest free number, the most urgent job. That is exactly what a heap gives you, in O(log n).

How it works

We’ll give each meeting a room. Meetings are half-open ranges [start, end), so a room whose meeting ends at 4 can host one that starts at 4. busy is a min-heap of (end, room) pairs, and free is a min-heap of room numbers.

Scroll through the steps and the graphic follows along. The top half is the timeline, with one row per room. The bottom half shows both heaps, smallest first. You can also press play, step with the arrow keys, or edit the meetings.

Sort by start. Now the clock only moves forward, and each meeting is handled once.
Take the next meeting. The clock jumps straight to its start, because nothing can happen in between.
The first meeting finds both heaps empty, so it opens room 0. A new room always gets the next unused number.
Book it: push (end, room) onto busy. Tuples compare by end first, so busy[0] is always the room that frees up first.
Before handing out a room, check busy[0]. Room 0 is busy until 7, but this meeting starts at 1. If even the earliest end is after start, every busy room is still in use.
When busy[0] ends at or before start, that room is free again. Pop it and push its number onto free. Room 1 ends at 4, just as the next meeting starts at 4, and that counts.
If free isn’t empty, reuse its top: the lowest free room number.
The check is a while loop, not an if. At time 8, room 1 (free since 6) and room 0 (free since 7) both come off busy.
free now holds rooms 0 and 1. Room 1 has been free for longer, but the rule is lowest number first, so room 0 wins. That’s why free rooms need a heap of their own.
Seven meetings fit in three rooms.

loading heap-scheduling…

Why it’s correct: once the release loop has run, busy holds exactly the rooms whose meetings are still running at start, and free holds every other room opened so far. The loop can stop at the first room that is still busy, because every room below it on the heap ends even later. So free[0] really is the lowest free room. A new room opens only when every existing room is busy, so when the count reaches rooms, that many meetings are running at the same moment. No schedule can use fewer.

import heapq


def assign_rooms(meetings):
    """meetings[i] = (start, end), a half-open time range [start, end).
    Each meeting gets the lowest-numbered room that is free when it starts.
    Returns (the room of each meeting, how many rooms were needed)."""
    order = sorted(range(len(meetings)), key=lambda i: (meetings[i][0], i))
    free = []                 # room numbers ready to reuse, lowest on top
    busy = []                 # (end, room) for rooms in use, earliest end on top
    rooms = 0
    room_of = [0] * len(meetings)
    for i in order:
        start, end = meetings[i]
        while busy and busy[0][0] <= start:
            _, room = heapq.heappop(busy)
            heapq.heappush(free, room)
        if free:
            room = heapq.heappop(free)
        else:
            room = rooms
            rooms += 1
        heapq.heappush(busy, (end, room))
        room_of[i] = room
    return room_of, rooms

#include <algorithm>
#include <functional>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

// meetings[i] = {start, end}, a half-open time range [start, end).
// Each meeting gets the lowest-numbered room that is free when it starts.
// Fills roomOf with the room of each meeting and returns how many rooms were needed.
int assignRooms(const vector<pair<int, int>>& meetings, vector<int>& roomOf) {
    int n = meetings.size();
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return make_pair(meetings[a].first, a) < make_pair(meetings[b].first, b);
    });
    priority_queue<int, vector<int>, greater<>> free;            // lowest room on top
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;   // (end, room)
    int rooms = 0;
    roomOf.assign(n, 0);
    for (int i : order) {
        auto [start, end] = meetings[i];
        while (!busy.empty() && busy.top().first <= start) {
            free.push(busy.top().second);
            busy.pop();
        }
        int room;
        if (!free.empty()) {
            room = free.top();
            free.pop();
        } else {
            room = rooms++;
        }
        busy.push({end, room});
        roomOf[i] = room;
    }
    return rooms;
}

import java.util.*;

class Rooms {
    // meetings[i] = {start, end}, a half-open time range [start, end).
    // Each meeting gets the lowest-numbered room that is free when it starts.
    // Fills roomOf with the room of each meeting and returns how many rooms were needed.
    static int assignRooms(int[][] meetings, int[] roomOf) {
        int n = meetings.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> meetings[a][0] != meetings[b][0]
            ? Integer.compare(meetings[a][0], meetings[b][0])
            : Integer.compare(a, b));
        PriorityQueue<Integer> free = new PriorityQueue<>();       // lowest room on top
        PriorityQueue<int[]> busy = new PriorityQueue<>(           // {end, room}
            (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
        int rooms = 0;
        for (int i : order) {
            int start = meetings[i][0], end = meetings[i][1];
            while (!busy.isEmpty() && busy.peek()[0] <= start) {
                free.add(busy.poll()[1]);
            }
            int room;
            if (!free.isEmpty()) {
                room = free.poll();
            } else {
                room = rooms++;
            }
            busy.add(new int[] {end, room});
            roomOf[i] = room;
        }
        return rooms;
    }
}

Just the count

If you only need the number of rooms, drop the room numbers and the free heap. Keep one min-heap of end times. For each meeting in start order, if the earliest end is <= start, that room is reused, so replace its end. Otherwise every room is busy, so push a new one. The heap never shrinks, and its final size is the answer.

import heapq

def rooms_needed(meetings):
    ends = []
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)   # reuse the room that freed up first
        else:
            heapq.heappush(ends, end)      # every room is busy: open one more
    return len(ends)

One if is enough here, because it doesn’t matter which free room you reuse. The two-heap version needs the while.

One CPU, the most urgent job first

Now turn it around: one worker, many jobs. Each job has an arrival time, a duration and a priority. Whenever the CPU is free, it runs the highest-priority job that has already arrived. The heap now holds jobs instead of rooms, ordered by priority.

The loop makes two moves. Push every job that has arrived by time onto the ready heap. Then pop the best one and move time on by its duration. If nothing is ready, the CPU is idle, so jump time to the next arrival.

import heapq


def run_jobs(jobs):
    """jobs[i] = (arrival, duration, priority). One CPU runs one job at a time.
    Whenever it is free, it starts the arrived job with the highest priority
    (the lower id on a tie). Returns the job ids in the order they run."""
    order = sorted(range(len(jobs)), key=lambda i: (jobs[i][0], i))
    ready = []                # (-priority, id): negate for a max-heap
    time, k, ran = 0, 0, []
    while k < len(order) or ready:
        if not ready:
            time = max(time, jobs[order[k]][0])      # idle: jump to the next arrival
        while k < len(order) and jobs[order[k]][0] <= time:
            i = order[k]
            heapq.heappush(ready, (-jobs[i][2], i))  # everything that has arrived
            k += 1
        _, i = heapq.heappop(ready)                  # the most urgent one runs
        ran.append(i)
        time += jobs[i][1]
    return ran

#include <algorithm>
#include <array>
#include <numeric>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

// jobs[i] = {arrival, duration, priority}. One CPU runs one job at a time.
// Whenever it is free, it starts the arrived job with the highest priority
// (the lower id on a tie). Returns the job ids in the order they run.
vector<int> runJobs(const vector<array<int, 3>>& jobs) {
    int n = jobs.size();
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return make_pair(jobs[a][0], a) < make_pair(jobs[b][0], b);
    });
    // Highest priority on top, then the lower id.
    auto later = [&](int a, int b) {
        return jobs[a][2] != jobs[b][2] ? jobs[a][2] < jobs[b][2] : a > b;
    };
    priority_queue<int, vector<int>, decltype(later)> ready(later);
    long long time = 0;
    int k = 0;
    vector<int> ran;
    while (k < n || !ready.empty()) {
        if (ready.empty()) {
            time = max(time, (long long)jobs[order[k]][0]);   // idle: jump to the next arrival
        }
        while (k < n && jobs[order[k]][0] <= time) {
            ready.push(order[k++]);                            // everything that has arrived
        }
        int i = ready.top();                                   // the most urgent one runs
        ready.pop();
        ran.push_back(i);
        time += jobs[i][1];
    }
    return ran;
}

import java.util.*;

class Cpu {
    // jobs[i] = {arrival, duration, priority}. One CPU runs one job at a time.
    // Whenever it is free, it starts the arrived job with the highest priority
    // (the lower id on a tie). Returns the job ids in the order they run.
    static int[] runJobs(int[][] jobs) {
        int n = jobs.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> jobs[a][0] != jobs[b][0]
            ? Integer.compare(jobs[a][0], jobs[b][0])
            : Integer.compare(a, b));
        // Highest priority on top, then the lower id.
        PriorityQueue<Integer> ready = new PriorityQueue<>((a, b) -> jobs[a][2] != jobs[b][2]
            ? Integer.compare(jobs[b][2], jobs[a][2])
            : Integer.compare(a, b));
        long time = 0;
        int k = 0;
        int[] ran = new int[n];
        int count = 0;
        while (k < n || !ready.isEmpty()) {
            if (ready.isEmpty()) {
                time = Math.max(time, jobs[order[k]][0]);    // idle: jump to the next arrival
            }
            while (k < n && jobs[order[k]][0] <= time) {
                ready.add(order[k++]);                       // everything that has arrived
            }
            int i = ready.poll();                            // the most urgent one runs
            ran[count++] = i;
            time += jobs[i][1];
        }
        return ran;
    }
}

Python’s heapq is a min-heap, so the code pushes -priority. The job’s id is the second field of the tuple, so ties go to the lower id. For the shortest job first, or the earliest deadline first, change only the key.

Lazy deletion

A heap can’t cheaply find or remove an item in the middle. Real schedulers need that: a job is cancelled, a deadline moves, a timer is reset. The fix is to leave the old entry in the heap and skip it when it reaches the top.

Keep each item’s current priority in a dictionary beside the heap. To add an item or change its priority, record the new value and push a new entry. When you pop, throw away every entry that doesn’t match the record.

import heapq

heap, current = [], {}               # current[job] = its live priority

def set_priority(job, prio):         # add or change: O(log n)
    current[job] = prio
    heapq.heappush(heap, (prio, job))

def cancel(job):                     # O(1): the old entry stays in the heap
    current.pop(job, None)

def pop_next():
    while heap:
        prio, job = heapq.heappop(heap)
        if current.get(job) == prio:   # skip cancelled and outdated entries
            del current[job]
            return job
    return None

Dijkstra’s algorithm with a library heap works the same way: a node’s old, longer distance stays in the heap and is skipped when it surfaces.

Why it’s O(n log n)

Sorting the meetings takes O(n log n). Each meeting is pushed onto busy once, so it can be popped at most once. The while loop may pop several rooms for one meeting and none for the next, but over the whole run it pops at most n times. Each room moves to free and back at most once per meeting. That’s O(n) heap operations, each O(log n).

part	time
sort by start	O(n log n)
pushes onto `busy`	n × O(log n)
pops from `busy`, whole run	at most n × O(log n)
pushes and pops on `free`	at most 2n × O(log n)
total	O(n log n)

Both heaps hold at most one entry per room, so with k rooms each operation is really O(log k). The CPU scheduler is the same: every job is pushed once and popped once. With lazy deletion, count every push, stale ones included. Each is popped at most once, so the cost is O(log m) per operation, where m is the number of pushes. Space is O(n).

Common mistakes

Releasing one room with `if`

Several rooms can free up between two meetings. With if, only the first moves to free. A meeting can then get a higher room number than it should, while a lower one sits empty on busy.

if busy and busy[0][0] <= start:      # ✗ frees at most one room
while busy and busy[0][0] <= start:   # ✓ frees every room that has ended

Getting the touching case wrong

With half-open ranges, a room freed at 4 can host a meeting that starts at 4. Using < keeps the room busy one step too long, and extra rooms get opened. If the statement says a room is still in use at its end time, < is right. Read it before you write the comparison.

while busy and busy[0][0] < start:    # ✗ [1, 4) and [4, 6) would need two rooms
while busy and busy[0][0] <= start:   # ✓ the room freed at 4 hosts the meeting at 4

Putting the wrong field first

A heap compares tuples field by field, starting with the first. (room, end) puts the lowest-numbered busy room on top, not the one that frees up first. In C++, forgetting greater<> is the same bug: priority_queue is a max-heap by default.

heapq.heappush(busy, (room, end))     # ✗ top = lowest room number
heapq.heappush(busy, (end, room))     # ✓ top = earliest end, lowest room on a tie

Ticking the clock

A loop that adds 1 to time gives the right answer but runs up to 10⁹ times. In the CPU loop, popping when nothing has arrived yet crashes on an empty heap. When nothing is ready, jump to the next event.

time += 1                                # ✗ one step per time unit
time = max(time, jobs[order[k]][0])      # ✓ idle: jump to the next arrival

Variations

Wait for a room. If no new rooms can be opened, a meeting that finds none free waits. Pop the busy room that frees up first and start the meeting at that room’s end time, keeping its length. Times can then grow past the input’s range, so use 64-bit integers in C++ and Java.
Earliest-free server, one heap. If any server will do, keep one heap of (free_time, server). Pop the top, start at max(arrival, free_time), and push back the new free time. Among idle servers this picks the one that has been idle longest, not the lowest number. You need two heaps only when the number decides.
Weighted servers. Order free by (weight, id) instead of by id alone. The same loop then picks the lightest free server.
Timer and retry queues. Push (due_time, seq, event). To handle everything due by now, pop while heap[0][0] <= now. A failed attempt goes back in with a later due time, such as now + base * 2 ** attempts. The sequence number keeps events with equal times in the order they were added.
Cooldowns. When a job type must wait n slots before it runs again, park it after it runs, together with the time it may return. Pick among the ready types with a max-heap of how many copies are left, and jump the clock when nothing is ready.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
Jobs arrive over time. There are k servers numbered 0 to k − 1, and each job must go to the lowest-numbered server that is idle when it arrives. What do you keep while you sweep the jobs in arrival order?
The busy heap tells you which servers have finished by each arrival; the free heap then gives the lowest number among them. A single (finish_time, server) heap, or a FIFO queue, hands out the server that has been idle longest, which is often not the lowest-numbered one.
2
What does this print?
```
import heapq
ends = []
for start, end in sorted([(0, 4), (4, 8), (1, 4), (4, 6)]):
    if ends and ends[0] <= start:
        heapq.heapreplace(ends, end)
    else:
        heapq.heappush(ends, end)
print(len(ends), ends[0])
```
Sorted, the meetings are (0, 4), (1, 4), (4, 6), (4, 8). The first two need two rooms, both ending at 4. With <=, each meeting starting at 4 reuses a room that ends at 4, so the heap stays at size 2 and ends as [6, 8]. Answering 4 treats touching meetings as overlapping, which is what < would do.

What does this print?

import heapq
heap, current = [], {}
def set_priority(job, prio):
    current[job] = prio
    heapq.heappush(heap, (prio, job))
def cancel(job):
    current.pop(job, None)
def pop_next():
    while heap:
        prio, job = heapq.heappop(heap)
        if current.get(job) == prio:
            del current[job]
            return job
    return None
set_priority("a", 5)
set_priority("b", 3)
set_priority("a", 1)
cancel("b")
print(pop_next(), pop_next(), len(heap))

4
This should give each meeting the lowest-numbered free room. On [[0, 5], [1, 3], [6, 7]] it returns [0, 1, 1] instead of [0, 1, 0]. What’s wrong?
```
import heapq
def assign(meetings):
    free, busy, rooms, out = [], [], 0, []
    for start, end in sorted(meetings):
        if busy and busy[0][0] <= start:
            heapq.heappush(free, heapq.heappop(busy)[1])
        if free:
            room = heapq.heappop(free)
        else:
            room, rooms = rooms, rooms + 1
        heapq.heappush(busy, (end, room))
        out.append(room)
    return out
```
By time 6 both rooms have ended, but if pops only the one that ended first, room 1, so it is the only choice. A while loop moves every ended room to free, and room 0 wins. Changing <= to < doesn’t help (3 and 5 are both before 6), and (room, end) would put room 0 on top even while it’s still busy.
5
The release loop is a while inside the loop over n meetings. Why is the whole algorithm still O(n log n), not O(n² log n)?
Count pops, not loop iterations per meeting. Every pop removes an entry that some meeting pushed, and there are only n pushes, so the total is at most n pops. One meeting can release many rooms (in the walkthrough, the meeting at 8 releases two), which is why “at most one per meeting” is false, but the total is still bounded.

Practice problems

Solve these right here, in Python, C++ or Java. Tests run as you go.

Scheduling with heaps

You’ll recognise it when

The idea

How it works

Just the count

One CPU, the most urgent job first

Lazy deletion

Why it’s O(n log n)

Common mistakes

Releasing one room with `if`

Getting the touching case wrong

Putting the wrong field first

Ticking the clock

Variations

Check yourself

Practice problems

Further reading

Just the count

One CPU, the most urgent job first

Lazy deletion

Releasing one room with if

Getting the touching case wrong

Putting the wrong field first

Ticking the clock

Releasing one room with `if`