Why this matters
A job scheduler runs many jobs on one worker. Some jobs must not run again too soon after they last ran. A service may need to wait before it retries the same request. A game may need a spell to recharge before it can be cast again. The question is simple to ask: given the jobs and the wait rule, what is the shortest total time to run all of them?
This lesson answers that question with a heap. A heap is a tree stored in an array where the most important item is always at the top. In C++ the standard std::priority_queue is a max heap by default, which means its top item is the largest. The heap in this lesson stores how many copies of each task are left, not the tasks themselves. You will also meet a plain queue, which is a line where the first item in is the first item out.
There are two ways to get the answer. The first is a simulation: we run the schedule one slot at a time and count the slots. The second is a formula that gives the same answer without simulating. We build the simulation first, because it is easy to trust, and then we use it to check the formula.
The problem in plain words
Each letter stands for one kind of task. The string AAABBB means three tasks of kind A and three tasks of kind B. Each task takes one time slot. A slot is one unit of time, the length of one job.
The cooldown n is the wait rule. After a task of some kind runs, the next task of the same kind must wait until n other slots have passed. With n equal to 2, if an A runs in slot 1, the next A can run in slot 4 at the earliest. Slots 2 and 3 must hold other tasks, or nothing.
If no task is allowed to run in a slot, the worker is idle for that slot. An idle slot still counts as time.
Take AAABBB with n equal to 2. One valid schedule is:
slot: 1 2 3 4 5 6 7 8
task: A B - A B - A BThe dash marks an idle slot. The schedule takes 8 slots, so the answer for this input is 8.
Could we do better? There are 6 tasks, so the answer is at least 6. But A B A B A B does not work. The A in slot 1 and the A in slot 3 have only one slot between them, and the rule needs two. So the 6 slot schedule is not allowed, and 8 is the minimum.
The idea: the most common task sets the pace
Think of each run of A as a frame. A frame is the A plus the n slots that must follow it, so a frame has n + 1 slots. With n equal to 2, a frame has 3 slots: A, then two other slots.
Three copies of A need three frames, but the last frame does not need its trailing slots, because nothing comes after it. So A takes two full frames and then one short row:
A B - A B - A BEach full frame has 3 slots, and the last row has 2 slots. The total is 3 + 3 + 2 = 8, which matches the answer.
The B tasks fill the empty slots. Here they fill the second slot of each frame. Once there are no more B tasks, the dashes stay idle.
Now suppose there were also three copies of C. The C tasks could take the empty slots, and no idle slot would be needed. The final row would then hold A, B and C, because all three have three copies. That is why the number of tasks that share the highest count matters.
This is the core of the answer. The most common task sets the number of frames, and the tasks that tie with it fill the last row.
Simulation with a max heap
The simulation runs one slot at a time. In each slot it does three things.
- If the first waiting task in the cooldown queue is ready, move it back into the heap.
- If the heap is not empty, take the task with the most copies left and run it in this slot. If it still has copies left after running, put it at the back of the cooldown queue.
- If the heap is empty, this slot is idle.
The simulation stops when the heap and the cooldown queue are both empty. The number of slots used is the answer.
The heap holds pairs of (copies left, letter). A pair with more copies is larger, so the top of the heap is always the task that has the most copies left. When two tasks have the same count, the letter breaks the tie, and the larger letter goes on top.
The cooldown queue holds tasks that just ran and are waiting. Each waiting task stores a field called readyAt, which is the first slot when the task may run again. A task that runs in slot t must wait n other slots, so it is ready again in slot t + n + 1. The queue is a good fit for this because the tasks enter in the order they ran, so their readyAt values rise from front to back. The front is always the first task to become ready.
Here is the simulation in full. It is a complete program, and the verbose flag prints one line per slot so you can follow it.
#include <array>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
using namespace std;
struct Waiting {
int copiesLeft;
char task;
int readyAt; // first slot when this task may run again
};
int leastInterval(const string& tasks, int n, bool verbose = false) {
array<int, 26> freq{};
for (char c : tasks) freq[c - 'A']++;
priority_queue<pair<int, char>> ready; // (copies left, task); largest first
for (int i = 0; i < 26; ++i)
if (freq[i] > 0) ready.push({freq[i], static_cast<char>('A' + i)});
queue<Waiting> cooling; // readyAt values rise from front to back
int slot = 0;
while (!ready.empty() || !cooling.empty()) {
slot++;
string back = "-";
if (!cooling.empty() && cooling.front().readyAt <= slot) {
ready.push({cooling.front().copiesLeft, cooling.front().task});
back = string(1, cooling.front().task);
cooling.pop();
}
string ran = "idle";
if (!ready.empty()) {
auto [left, task] = ready.top();
ready.pop();
ran = string(1, task);
if (left - 1 > 0) cooling.push({left - 1, task, slot + n + 1});
}
if (verbose)
cout << "slot " << slot << ": ran " << ran << ", back from cooldown " << back << "\n";
}
return slot;
}
int main() {
int total = leastInterval("AAABBB", 2, true);
cout << "answer " << total << "\n";
}Compile it with g++ -std=c++20 -Wall -o scheduler scheduler.cpp and run ./scheduler. The program prints this:
slot 1: ran B, back from cooldown -
slot 2: ran A, back from cooldown -
slot 3: ran idle, back from cooldown -
slot 4: ran B, back from cooldown B
slot 5: ran A, back from cooldown A
slot 6: ran idle, back from cooldown -
slot 7: ran B, back from cooldown B
slot 8: ran A, back from cooldown A
answer 8B runs first, not A. Both letters have three copies, and the heap compares the letter second, so B is larger and sits on top. Either order gives 8. The idle slots are 3 and 6, which match the dashes in the picture earlier.
Slot 3 is idle. B ran in slot 1, so its readyAt is 1 + 2 + 1 = 4, and A ran in slot 2, so its readyAt is 5. Nothing is ready in slot 3, and the heap is empty, so the worker waits.
In slot 4, B is released into the heap with two copies left, and it runs. Slot 5 works the same way for A. The trace also shows that the wait is respected: no task ever runs in the slot right after its own last run.
The cost of this method is one heap step per slot. The heap never holds more than 26 items, so each heap step is short. But the loop runs once for every slot, including idle slots. The number of slots is the answer, which can be large when n is large. A schedule of 100,000 slots takes 100,000 loop steps. That is fine for many inputs, and it is also why the formula is useful.
Checking with a formula
The frame picture gives a formula. Let m be the largest number of copies any single task has. Let k be the number of tasks that have exactly m copies.
The first m - 1 frames each take n + 1 slots. The last row takes k slots, one for each task with m copies. So the schedule needs
(m - 1) * (n + 1) + kslots when there are enough other tasks to fill every empty slot in the frames.
Sometimes the other tasks are too few to fill the empty slots. In that case idle slots are needed, and the formula above is the answer. Sometimes there are so many tasks that no slot is idle, and the answer is just the number of tasks. The minimum is therefore the larger of the two numbers:
answer = max(number of tasks, (m - 1) * (n + 1) + k)Check this on AAABBB with n equal to 2. The largest count is m = 3, and two tasks have that count, so k = 2. The formula gives (3 - 1) * (2 + 1) + 2 = 8. The number of tasks is 6, so the answer is max(6, 8) = 8. That matches the simulation.
Here is the formula in code. It needs no heap, and it runs in the time it takes to count letters.
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
using namespace std;
int leastIntervalFormula(const string& tasks, int n) {
array<int, 26> freq{};
for (char c : tasks) freq[c - 'A']++;
int maxFreq = *max_element(freq.begin(), freq.end());
int countMax = 0;
for (int f : freq)
if (f == maxFreq) countMax++;
int frames = (maxFreq - 1) * (n + 1) + countMax;
return max(static_cast<int>(tasks.size()), frames);
}
int main() {
cout << leastIntervalFormula("AAABBB", 2) << "\n";
}The program prints 8.
Worked examples of increasing difficulty
The first example is the easiest case, where the tasks fill every slot.
Take ABCABC with n equal to 2. Each letter has two copies, so m is 2, and three letters tie, so k is 3. The frame count is (2 - 1) * 3 + 3 = 6. There are also 6 tasks. The answer is 6, so no idle slot is needed. Here is one such schedule: A B C A B C. Between the two A runs there are B and C, which is two slots, so the cooldown rule holds.
The second example is larger, with two letters that tie at the top and tasks that fill the gaps.
Take AAAABBBBCCDD with n equal to 2. A and B each have four copies, so m is 4 and k is 2. The frame count is (4 - 1) * 3 + 2 = 11. There are 12 tasks, so the answer is max(12, 11) = 12. The formula says that the 12 tasks fill the schedule with no idle slot, and the simulation gives the same number.
The third example has one task that dominates and many small tasks.
Take AAAAAABCDEFG with n equal to 2. A has six copies, and no other letter does, so m is 6 and k is 1. The frame count is (6 - 1) * 3 + 1 = 16. The number of tasks is 12. The answer is max(12, 16) = 16.
Here is the picture. Each of the first five A tasks is followed by a gap of two slots, so there are ten gap slots. The six small tasks fill six of them, and the other four are idle. The total is 6 A tasks, 6 small tasks, and 4 idle slots, which is 16.
Here is a program that prints the simulation and the formula side by side for these examples, and then checks them on random inputs. The random inputs use one to five kinds of task, up to 30 tasks, and cooldowns from 0 to 5.
#include <algorithm>
#include <array>
#include <iostream>
#include <queue>
#include <random>
#include <string>
#include <utility>
#include <vector>
using namespace std;
struct Waiting {
int copiesLeft;
char task;
int readyAt;
};
int leastInterval(const string& tasks, int n) {
array<int, 26> freq{};
for (char c : tasks) freq[c - 'A']++;
priority_queue<pair<int, char>> ready;
for (int i = 0; i < 26; ++i)
if (freq[i] > 0) ready.push({freq[i], static_cast<char>('A' + i)});
queue<Waiting> cooling;
int slot = 0;
while (!ready.empty() || !cooling.empty()) {
slot++;
if (!cooling.empty() && cooling.front().readyAt <= slot) {
ready.push({cooling.front().copiesLeft, cooling.front().task});
cooling.pop();
}
if (!ready.empty()) {
auto [left, task] = ready.top();
ready.pop();
if (left - 1 > 0) cooling.push({left - 1, task, slot + n + 1});
}
}
return slot;
}
int leastIntervalFormula(const string& tasks, int n) {
array<int, 26> freq{};
for (char c : tasks) freq[c - 'A']++;
int maxFreq = *max_element(freq.begin(), freq.end());
int countMax = 0;
for (int f : freq)
if (f == maxFreq) countMax++;
int frames = (maxFreq - 1) * (n + 1) + countMax;
return max(static_cast<int>(tasks.size()), frames);
}
int main() {
vector<pair<string, int>> examples = {
{"AAABBB", 2}, {"ABCABC", 2}, {"AAAABBBBCCDD", 2}, {"AAAAAABCDEFG", 2}};
for (const auto& [tasks, n] : examples)
cout << tasks << " n=" << n << ": simulation " << leastInterval(tasks, n)
<< ", formula " << leastIntervalFormula(tasks, n) << "\n";
mt19937 rng(99);
int mismatches = 0;
for (int it = 0; it < 200000; ++it) {
int kinds = 1 + rng() % 5, len = 1 + rng() % 30, n = rng() % 6;
string s;
for (int i = 0; i < len; ++i) s += char('A' + rng() % kinds);
if (leastInterval(s, n) != leastIntervalFormula(s, n)) mismatches++;
}
cout << "random inputs that disagree: " << mismatches << "\n";
}The program prints:
AAABBB n=2: simulation 8, formula 8
ABCABC n=2: simulation 6, formula 6
AAAABBBBCCDD n=2: simulation 12, formula 12
AAAAAABCDEFG n=2: simulation 16, formula 16
random inputs that disagree: 0The two methods agreed on all 200,000 random inputs. The formula is the faster method, and the simulation is the easier one to explain. Use the simulation to understand a schedule, and the formula to answer quickly.
Common mistakes
The most common mistake is to forget the tie count. Without it, the formula for AAABBB with n equal to 2 gives 6, but the correct answer is 8. Here is the broken line on its own:
int frames = (maxFreq - 1) * (n + 1);With AAABBB and n equal to 2, that line gives (3 - 1) * 3 = 6, not 8. The fix is to add the number of tasks that share the highest count. The last row of the picture has two slots, one for A and one for B, and the formula must count both.
The second mistake is an off-by-one in the cooldown. The task that runs in slot t can run again in slot t + n + 1. If you write slot + n, the wait becomes one slot too short. For AAABBB with n equal to 2, the schedule then puts A in slot 2 and again in slot 4, with only B between them. The program reports 6, which is not allowed. The correct value is 8. When you test a cooldown rule, check that the number of slots between two runs of the same task is exactly n.
The third mistake is to use a min heap by accident. The default std::priority_queue puts the largest item on top. To get the smallest first, you must pass a comparator. Here is a short program that makes this mistake:
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
int main() {
priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> ready;
ready.push({3, 'A'});
ready.push({2, 'B'});
ready.push({1, 'C'});
cout << "first out: " << ready.top().second << " with " << ready.top().first << " copies\n";
}It prints first out: C with 1 copies. The task with the most copies, A, is the last one to come out. A scheduler built this way takes the task with the fewest copies left at every slot, which is the opposite of the rule. The fix is to remove the greater comparator, so the heap uses its default order.
The fourth mistake is to forget an include. If you use priority_queue without #include <queue>, the compiler stops with an error. Compiling a program that has only #include <iostream> gives this message:
mist1.cpp:4:5: error: ‘priority_queue’ was not declared in this scope
4 | priority_queue<int> heap;
| ^~~~~~~~~~~~~~The fix is to add the line #include <queue> at the top of the file.
The fifth mistake is to call top() on an empty heap. The top() call returns the largest item, and an empty heap has none. The C++ standard leaves this undefined, which means the program may crash or return junk. With the GNU C++ library that ships with g++ 15 on Ubuntu, the check runs at run time and stops the program. Here is a program that makes the mistake:
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> heap;
cout << heap.top() << "\n";
}The run prints an assertion message, and the important part is the last words of the line:
Assertion '!this->empty()' failed.The fix is to check empty() before every top() call. The scheduler's loop does this with while (!ready.empty() || !cooling.empty()), and it checks ready.empty() again before taking the top.
The sixth mistake is to keep a reference to the top after popping it. A reference is a second name for the same memory. After pop(), the old top slot is gone, so the reference no longer points at the value you read.
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> heap;
heap.push(4);
heap.push(7);
const int& best = heap.top();
heap.pop();
cout << "best after pop: " << best << "\n";
}This prints best after pop: 4, but the top was 7. The reference now points at a slot that the heap has reused, so the value is wrong. The fix is to copy the value before popping, as auto [left, task] = ready.top(); does in the scheduler. The copy is made first, and the pop comes second.
Practice
- Use the formula to find the answer for
AAAAAAwithnequal to 2. Show your working.
Show the answer
Here m is 6, and only A has that count, so k is 1. The frame count is (6 - 1) * (2 + 1) + 1 = 16. The number of tasks is 6, and max(6, 16) is 16. The schedule is A, two other slots, and so on five times, then a final A. Each of the five gaps is two slots with nothing else to fill them, so the gaps are idle.
- The answer for
ABCABCwithnequal to 2 is 6, and the answer forAABBCCwithnequal to 2 is also 6. Explain why no idle slot is needed in either case.
Show the answer
Each letter has two copies, so m is 2 and k is 3. The frame count is (2 - 1) * 3 + 3 = 6, and there are 6 tasks. The three letters that tie can fill the second and third slot of every frame. No slot is left empty, so the answer equals the number of tasks.
- In the trace for
AAABBBwithnequal to 2, which task runs in slot 1, and why?
Show the answer
B runs in slot 1. Both A and B have three copies, so the heap compares the letters. The pair is (3, 'B') and (3, 'A'), and the larger pair is on top. The letter B is larger than A, so B comes first.
- The answer for
AABBCCDDEEwithnequal to 1 is 10. Use the formula to check this without running the simulation.
Show the answer
Each letter has two copies, so m is 2. Five letters tie at that count, so k is 5. The frame count is (2 - 1) * (1 + 1) + 5 = 7. The number of tasks is 10. The answer is max(10, 7), which is 10. The five letters with two copies each fill all the slots, so no idle slot is needed.
- Change the cooldown rule in the simulation so that a task ready time is
slot + ninstead ofslot + n + 1. Predict the answer forAAABBBwithnequal to 2, then run the code to check.
Show the answer
The answer becomes 6. The schedule is B A B A B A. The A runs in slots 2, 4 and 6, so between two A runs there is only one slot, but the rule needs two. The simulation accepts that schedule because the ready time is one slot too early. The correct rule is slot + n + 1, which gives 8.
Summary
- A cooldown of
nmeans a task must waitnother slots before it can run again, so it is readyn + 1slots after its last run. - A max heap of (copies left, task) gives the task with the most copies left at the top, which is the one to run next.
- A queue holds tasks that are cooling down, and their ready times rise from front to back, so the front is always the first to become ready.
- The answer is the larger of the number of tasks and
(m - 1) * (n + 1) + k, wheremis the largest count andkis how many tasks share it. - Check the formula against the simulation, and check the simulation by hand on a small example.