cf.completefrontend
HEAPS & PRIORITY QUEUES · CORE

Scheduling with a heap

Simulate time moving forward and use a heap to pick the most urgent job among those that are ready.

Time O(n log n)Space O(n)7 practice problemsStep-through picture

The idea

Many tasks are about running jobs over time: jobs arrive at different moments, and whenever a worker is free you must choose which waiting job to run next. The rule might be "shortest job first", "highest priority first", or "earliest deadline first".

The pattern has two parts. First sort the jobs by arrival time, and keep a next index for the first job that hasn't arrived yet. Then keep a heap called ready with the jobs that have arrived but haven't run, ordered by your rule.

The simulation repeats: move every job that has arrived by the current time from the sorted list into ready. Pop the best job, run it, and move time forward by its length. If nothing is ready, jump time to the next arrival instead of waiting one tick at a time.

An everyday example

A clinic's waiting room

Patients arrive at a clinic over the day. When the doctor is free, the nurse looks only at people already in the waiting room and calls the one whose visit is quickest. People who haven't arrived yet can't be called. If the room is empty, the doctor waits until the next patient walks in.

How the example maps to the code
In the exampleIn the code
The list of appointments by arrival timejobs, sorted by arrive
Patients in the waiting roomthe ready heap
The clock on the walltime
Calling the quickest visitready.pop()
Waiting for the next patient when the room is emptytime = jobs[next].arrive

From the slow way to scheduling with a heap

  1. The obvious simulation ticks a clock one unit at a time. At each tick it scans every job to see which have arrived and not run, and picks the shortest. That costs a full scan per tick, and the number of ticks depends on how big the times are, not on how many jobs there are: arrival times near a billion mean a billion ticks.
  2. Two ideas remove most of that waste. First, arrival times are known up front, so sort the jobs by arrive once and keep a pointer next to the first job that hasn't arrived yet. Releasing every arrived job is then a short while loop, and each job is released exactly once in the whole run.
  3. Second, the waiting jobs form a group that new jobs keep joining while you always take the best one. That is a min-heap, called ready and ordered by length and then by id. Picking the next job becomes a pop, O(log n), instead of a scan over every waiting job.
  4. Last, the clock doesn't need to tick. It only changes when a job finishes, time += job.length, or, when nothing is waiting, when the next job arrives, time = jobs[next].arrive. Release arrived jobs, jump if idle, otherwise run the best ready job: that loop is scheduling with a heap.

How it works

  1. Turn each task into { arrive, length, id } and sort jobs by arrival time.
  2. Make ready, a heap ordered by length, then by id to break ties.
  3. Start time at 0 and next at 0.
  4. Move every job with arrive <= time into ready, advancing next.
  5. If ready is empty, jump time to jobs[next].arrive and go back to the previous step.
  6. Otherwise pop the shortest job, record its id, and add its length to time. Repeat until every job has run.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function shortestJobFirst(tasks) {
  2. const jobs = tasks.map(([arrive, length], id) => ({ arrive, length, id }));
  3. jobs.sort((a, b) => a.arrive - b.arrive || a.id - b.id);
  4. const ready = new MinHeap((a, b) => a.length - b.length || a.id - b.id);
  5. const order = [];
  6. let time = 0;
  7. let next = 0;
  8. while (order.length < jobs.length) {
  9. while (next < jobs.length && jobs[next].arrive <= time) {
  10. ready.push(jobs[next]);
  11. next++;
  12. }
  13. if (ready.size === 0) {
  14. time = jobs[next].arrive;
  15. continue;
  16. }
  17. const job = ready.pop();
  18. order.push(job.id);
  19. time += job.length;
  20. }
  21. return order;
  22. }

How fast it is

TimeO(n log n)
Extra memoryO(n)

Sorting is O(n log n). Each job is pushed and popped once on a heap of up to n jobs. The clock jumps over idle time, so it adds no extra loops.

  • Best caseO(n log n)

    Even if no two jobs ever wait at the same time, the sort costs O(n log n). The heap part is then cheap: each job goes into an empty heap and comes right back out.

  • Average caseO(n log n)

    The sort, plus one push and one pop per job on a heap of up to n jobs.

  • Worst caseO(n log n)

    All jobs arrive at time 0, so ready holds all n of them and every pop travels the heap's full height, about log₂ n levels.

Common mistakes

  • Putting all jobs in the heap at the start. Jobs that haven't arrived yet could then be picked too early.
  • Advancing time by 1 while idle. With arrival times like 1000000000, the loop never finishes. Jump straight to the next arrival.
  • Not breaking ties. Equal lengths or priorities can come out in different orders. Add a second key like id.
  • Popping only one arrival per loop instead of all jobs that have arrived. Use a while loop to release every arrived job.

When to use it

Look for these clues in a problem:

  • Jobs, requests, or meetings have start or arrival times, and you choose an order to run them.
  • The question asks for the order jobs finish, the total waiting time, or how many workers or rooms are needed.
  • At each moment, the next choice is "the best among those currently available".
  • There are cooldowns or deadlines, and the most urgent available item should go first.

Check yourself

Answer each one in your head first, then open it.

Why not put every job in the heap at the start?

Then a short job that arrives later could be picked before it exists. Only released jobs, with arrive <= time, may be chosen.

Why does the release step use while and not if?

Several jobs can arrive while one job runs. In the trace, jobs 1, 2, and 3 all arrived by time 7 and all had to join ready before the next pick.

When ready is empty, why is jobs[next] sure to exist?

The loop only runs while some job hasn't run. If none is waiting, the remaining jobs haven't arrived yet, so next points to one of them.

How many times can the outer loop run for n jobs?

At most 2n: once per job that runs, plus at most one jump before each run. In the trace, 6 runs and 2 jumps made 8 loops.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Three facts hold at the top of each loop: every job before index next has been released, ready holds exactly the released jobs that haven't run, and time is the moment the worker becomes free. They hold at the start, with time = 0, next = 0, and an empty ready.

The inner while releases every job with arrive <= time. Because jobs is sorted by arrival, these are exactly the jobs from next up to the first one still in the future, so afterwards ready holds every job that has arrived and not run. Popping the heap picks the shortest of them, with the smaller id on ties, which is exactly the rule. Adding its length to time moves the clock to when the worker is free again.

If ready is empty, no job is waiting, so nothing can happen before jobs[next].arrive, and jumping there skips only idle time. jobs[next] must exist, because some job hasn't run yet and every released job has. Each loop either runs a job or jumps to a time when at least one job will be released, so after at most 2n loops every job has run.

Going deeper

3 more ideas

Why sort first and use a heap

Arrivals are known in advance, so sorting them once lets next sweep forward and add each job exactly once. The choice among ready jobs keeps changing as new ones arrive, which is exactly what a heap is good at: adding items at any time and always taking the best one.

A related shape: counting rooms or workers

To find how many rooms a set of meetings needs, sort meetings by start time and keep a min-heap of end times for rooms in use. For each meeting, if the earliest end time is at or before its start, that room is free: pop it. Then push this meeting's end. The heap's size at the end is the number of rooms needed.

Time and memory

Sorting costs O(n log n). Each job enters and leaves the heap once, O(log n) each. Jumping time forward when nothing is ready means empty stretches cost nothing. In total O(n log n) time and O(n) memory.

Work it by hand

Every step in a table, with why

Run six jobs, shortest first among those that have arrived. Each task is [arrive, length], and its index is its id.

tasks = [[2, 5], [3, 2], [4, 7], [6, 2], [20, 3], [21, 1]]

SteptimeReleasedRun or jumpready lefttime afterorderWhy
10nonejump to 2empty2[]No job has arrived by time 0 and ready is empty, so the clock jumps straight to the first arrival.
22job 0run job 0 (length 5)empty7[0]Job 0 is the only one waiting, so it runs from 2 to 7. Jobs 1, 2, and 3 arrive while it runs, but they don't interrupt it.
37jobs 1, 2, 3run job 1 (length 2)jobs 3, 29[0, 1]Three jobs arrived by time 7. Jobs 1 and 3 both have length 2, and the tie goes to the smaller id, job 1.
49nonerun job 3 (length 2)job 211[0, 1, 3]The shortest waiting job is now job 3.
511nonerun job 2 (length 7)empty18[0, 1, 3, 2]Job 2 arrived at time 4 but waited the longest, because every other waiting job was shorter.
618nonejump to 20empty20[0, 1, 3, 2]Nothing is waiting and job 4 arrives at 20, so the clock skips the idle time in one step.
720job 4run job 4 (length 3)empty23[0, 1, 3, 2, 4]Job 5 arrives at 21, while job 4 is running, so it can't be picked yet.
823job 5run job 5 (length 1)empty24[0, 1, 3, 2, 4, 5]The last job runs. order.length now equals jobs.length, so the loop ends.

The order is [0, 1, 3, 2, 4, 5], and the last job finishes at time 24. The outer loop ran 8 times for 6 jobs: 6 runs and 2 jumps. The clock never ticked one unit at a time.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Scheduling with a heapO(n log n)O(n)Jobs arrive over time and you repeatedly pick the best waiting one by some rule.
Scan all waiting jobs each timeO(n²)O(n)There are only a few dozen jobs, so a plain array and a scan are simpler and fast enough.
Sort by the rule onceO(n log n)O(n)All jobs are available from the start, so arrival times don't matter and one sort gives the whole order.

Extra memory: O(n): the jobs copy, the ready heap, and order.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Scheduling with a heap and the other approaches, on a scale where each line up is 10 times more steps.
  • Scheduling with a heap, Sort by the rule once O(n log n)
  • Scan all waiting jobs each time O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Scheduling with a heap339,96620 million
Scan all waiting jobs each time1001 million1 trillion
Sort by the rule once339,96620 million

Inputs that need care

6 tricky inputs
No tasks: tasks = []
order.length < jobs.length is 0 < 0, which is false, so it returns [] without ever reading jobs[next].
All jobs arrive at once: [[0, 4], [0, 1], [0, 3]]
All three are released in the first loop and run shortest first: [1, 2, 0]. This is plain sorting by length, done with a heap.
Equal lengths: jobs 1 and 3 in the trace
The compare a.length - b.length || a.id - b.id breaks the tie by id, so the result never depends on the heap's internal order.
A long idle gap: arrivals at 0 and 1000000000
One jump moves time across the gap. A clock that ticked by 1 would loop a billion times.
Tasks given out of arrival order: [[5, 1], [0, 2]]
The sort puts the second task first, but each job keeps its original index as id, so the answer [1, 0] still refers to positions in tasks.
A job of length 0: [[0, 0], [0, 2], [1, 1]]
It runs first and time doesn't move. The next loop releases nothing new and picks the next ready job, so the result [0, 1, 2] is still correct.

Variations and follow-ups

Twists interviewers add

Several workers

With w workers, keep a second min-heap of the times when each worker becomes free. Pop the earliest free worker, move time to at least its free time, release arrived jobs, run the best one on that worker, and push the worker back with its new free time.

Other rules

Only the compare function changes: highest priority first is b.priority - a.priority, and earliest deadline first is a.deadline - b.deadline. The release-and-jump loop stays exactly the same.

Jobs that can be paused

If a running job can be paused when a shorter one arrives (shortest remaining time first), run only until the next arrival, if one is still to come: Math.min(job.length, jobs[next].arrive - time) units. If the job isn't done, push it back with its remaining length.

Cooldowns between equal tasks

For "tasks of the same type must be at least n units apart", keep a max-heap of remaining counts and a queue of tasks that are cooling down, each with the time it becomes ready again. At each step, move ready tasks from the queue back into the heap, then run the top one.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from jobs, tasks, or requests with arrival or start times, plus a rule for which waiting one goes next: "shortest first", "highest priority", or "earliest deadline".
  • Describe the three parts before coding: jobs sorted by arrival with a next pointer, a heap of ready jobs ordered by the rule, and a clock that jumps instead of ticking.
  • Ask how ties should be broken, and put the tie-break in the compare function. Many wrong answers to these problems are only wrong on ties.
  • Test by hand: an idle gap at the start, an idle gap in the middle, two jobs with equal length, and all jobs arriving at once.
  • A common follow-up: "what if there are k workers?". Answer: add a min-heap of the times each worker becomes free, and always give the next job to the worker that is free first.

Where frontend code uses it

The same idea in real UI code
  • React's scheduler keeps tasks in a min-heap and, whenever the browser gives it time, runs the task with the earliest expiration first.
  • A notification queue shows the most important toast first, among the ones that are ready to show, and new ones keep arriving.
  • A build tool or test runner with a fixed number of workers can start the longest jobs first to finish sooner, picking from a heap of ready jobs.
  • A calendar app that tells you how many meeting rooms a day needs sorts meetings and keeps a heap of end times.

Related algorithms