Task Scheduler: Two Answers That Have To Match
LeetCode 621 has two unrelated correct solutions — a heap simulation and a one-line formula — so running them against every task multiset up to size 14 crossed with every cooldown from 0 to 40 is a stronger test than any example you would write by hand.
Task Scheduler: Two Answers That Have To Match
LeetCode 621 hands you a bag of CPU tasks labelled A through Z and a cooldown n. Two runs of
the same task must be at least n ticks apart. You want the shortest total schedule.
It is one of the few interview problems with two completely unrelated correct answers. One is a simulation — a max-heap, a cooldown queue, a clock that ticks. The other is arithmetic:
(maxFreq - 1) * (n + 1) + maxFreqCountNo loop over time, no queue, no heap. They share no data structure and no control flow. If both are right they must return the same integer on every input that exists, and that is a much stronger test than any handful of examples you could write by hand.
So build both and point them at each other.
The formula
Take the most frequent task. Call how often it appears maxFreq. Every pair of consecutive
occurrences has to be n + 1 ticks apart — the task itself, plus n slots you have to fill with
something else or leave idle. With maxFreq copies you get maxFreq - 1 such blocks, each n + 1
wide. Then the last copy costs one more tick.
If several tasks tie for the top frequency, they all have to appear in that final block, so the
tail is maxFreqCount rather than 1.
That skeleton is a lower bound, not the answer. It counts the slots the bottleneck forces into existence. If you have more tasks than slots, the extra ones do not compress — they extend the schedule, one tick each, and nothing idles at all.
function leastIntervalFormula(tasks, n) {
const counts = new Map();
for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);
if (counts.size === 0) return 0;
let maxFreq = 0;
for (const c of counts.values()) if (c > maxFreq) maxFreq = c;
let maxFreqCount = 0;
for (const c of counts.values()) if (c === maxFreq) maxFreqCount++;
const skeleton = (maxFreq - 1) * (n + 1) + maxFreqCount;
return Math.max(skeleton, tasks.length);
}Hold on to the counts.size === 0 guard and the Math.max. Both of them come back later, and one
of them comes back as the whole point of this article.
The simulation
The simulation does not know any of that. It pops the task with the most work left, runs it, and parks it until its cooldown expires.
class CountHeap {
constructor() { this.a = []; }
get size() { return this.a.length; }
push(v) {
this.a.push(v);
let i = this.a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.a[p] >= this.a[i]) break;
[this.a[p], this.a[i]] = [this.a[i], this.a[p]];
i = p;
}
}
pop() {
const top = this.a[0];
const last = this.a.pop();
if (this.a.length > 0) {
this.a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let big = i;
if (l < this.a.length && this.a[l] > this.a[big]) big = l;
if (r < this.a.length && this.a[r] > this.a[big]) big = r;
if (big === i) break;
[this.a[big], this.a[i]] = [this.a[i], this.a[big]];
i = big;
}
}
return top;
}
}
function leastIntervalHeap(tasks, n) {
const counts = new Map();
for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);
const heap = new CountHeap();
for (const c of counts.values()) heap.push(c);
const cooling = [];
let head = 0;
let time = 0;
while (heap.size > 0 || head < cooling.length) {
time++;
if (heap.size > 0) {
const remaining = heap.pop() - 1;
if (remaining > 0) cooling.push({ count: remaining, readyAt: time + n });
}
// drained after the pop, so a task released at tick T runs at T + 1 at the earliest
if (head < cooling.length && cooling[head].readyAt === time) {
heap.push(cooling[head++].count);
}
}
return time;
}Two details worth naming. The queue is drained after the pop, not before — a task released on
tick T is not eligible until T + 1, which is what makes readyAt = time + n come out to a
genuine n-tick gap rather than n - 1. And cooling is walked with a head index instead of
Array.shift(). Here that is a wash, because the queue never holds more than one entry per distinct
task, but the habit costs nothing.
Agreeing is not the same as being right
Two implementations can agree because they share a misconception. Before trusting the comparison I want a third opinion that is slow, stupid and obviously correct: try every legal move at every tick and keep the best.
function leastIntervalOracle(counts, n) {
const memo = new Map();
const key = (c, cd) =>
c.map((v, i) => [v, cd[i]])
.filter(p => p[0] > 0)
.sort((x, y) => x[0] - y[0] || x[1] - y[1])
.join('|');
function search(c, cd) {
if (c.every(v => v === 0)) return 0;
const k = key(c, cd);
if (memo.has(k)) return memo.get(k);
let best = Infinity, ranSomething = false;
for (let i = 0; i < c.length; i++) {
if (c[i] > 0 && cd[i] === 0) {
ranSomething = true;
const c2 = c.slice(); c2[i]--;
const cd2 = cd.map(x => Math.max(0, x - 1));
cd2[i] = c2[i] > 0 ? n : 0;
best = Math.min(best, 1 + search(c2, cd2));
}
}
if (!ranSomething) best = 1 + search(c, cd.map(x => Math.max(0, x - 1)));
memo.set(k, best);
return best;
}
return search(counts, counts.map(() => 0));
}The memo key throws away task identity and sorts, because two tasks with the same remaining count and the same cooldown are interchangeable. Without that the search explodes past six tasks.
Enumerating the input space
Task identity does not matter to the answer either — only the multiset of frequencies does. AAB
and BBC are the same problem. So the input space is integer partitions, crossed with n.
const ALPHABET = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
function* countShapes(total, cap) {
if (total === 0) { yield []; return; }
for (let part = Math.min(total, cap); part >= 1; part--)
for (const rest of countShapes(total - part, part)) yield [part, ...rest];
}
function shapeToTasks(shape) {
const out = [];
shape.forEach((c, i) => { for (let j = 0; j < c; j++) out.push(ALPHABET[i]); });
return out;
}
function crossExamine({ maxTotal, maxN, oracleUpTo }) {
let checked = 0, formulaVsHeap = 0, formulaVsOracle = 0, heapVsOracle = 0;
const splits = [];
for (let total = 0; total <= maxTotal; total++) {
for (const shape of countShapes(total, Math.max(total, 1))) {
if (shape.length > 26) continue;
const tasks = shapeToTasks(shape);
for (let n = 0; n <= maxN; n++) {
checked++;
const f = leastIntervalFormula(tasks, n);
const h = leastIntervalHeap(tasks, n);
if (f !== h) { formulaVsHeap++; if (splits.length < 5) splits.push({ shape, n, f, h }); }
if (total <= oracleUpTo) {
const o = leastIntervalOracle(shape, n);
if (f !== o) formulaVsOracle++;
if (h !== o) heapVsOracle++;
}
}
}
}
return { checked, formulaVsHeap, formulaVsOracle, heapVsOracle, splits };
}
const t0 = process.hrtime.bigint();
const report = crossExamine({ maxTotal: 14, maxN: 40, oracleUpTo: 9 });
const elapsedMs = Number(process.hrtime.bigint() - t0) / 1e6;
console.log(report.checked, 'inputs in', elapsedMs.toFixed(0) + 'ms');
console.log('formula vs heap :', report.formulaVsHeap);
console.log('formula vs oracle:', report.formulaVsOracle);
console.log('heap vs oracle:', report.heapVsOracle);
console.log('splits:', JSON.stringify(report.splits));On Node 22.23.2:
20828 inputs in 301ms
formula vs heap : 0
formula vs oracle: 0
heap vs oracle: 0
splits: []Every task multiset of size 0 through 14, every n from 0 to 40, three independent answers, no
split. Now the interesting part is what that took.
The near-misses
The cross-examination is boring because two guards are doing work. Delete either and it stops being boring.
Take out the Math.max and keep only the skeleton:
function skeletonOnly(tasks, n) {
const counts = new Map();
for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);
if (counts.size === 0) return 0;
const maxFreq = Math.max(...counts.values());
let k = 0; for (const c of counts.values()) if (c === maxFreq) k++;
return (maxFreq - 1) * (n + 1) + k;
}
for (const [tasks, n] of [[['A','A','B','B'], 0], [['A','A','A','B','C','D','E','F','G'], 1]]) {
console.log(tasks.join(''), 'n=' + n, 'skeleton', skeletonOnly(tasks, n),
'heap', leastIntervalHeap(tasks, n));
}AABB n=0 skeleton 3 heap 4
AAABCDEFG n=1 skeleton 5 heap 9AABB with n = 0 is the smallest one I found. No cooldown at all, four tasks, four ticks — and
the skeleton says three, because (2 - 1) * 1 + 2 = 3 describes a structure with room for three
things when you have four. The nine-task case is louder: the skeleton is measuring idle capacity,
and once there are more fillers than idle slots the CPU stops idling and the answer is just
tasks.length. n = 0 and "lots of distinct tasks" are the two directions that expose it, and both
are one keystroke for an interviewer to type.
The other guard is the heap's siftDown. A version that only ever compares the left child:
class BrokenHeap extends CountHeap {
pop() {
const top = this.a[0];
const last = this.a.pop();
if (this.a.length > 0) {
this.a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1;
if (l >= this.a.length || this.a[l] <= this.a[i]) break;
[this.a[l], this.a[i]] = [this.a[i], this.a[l]];
i = l;
}
}
return top;
}
}
function leastIntervalBrokenHeap(tasks, n) {
const counts = new Map();
for (const t of tasks) counts.set(t, (counts.get(t) || 0) + 1);
const heap = new BrokenHeap();
for (const c of counts.values()) heap.push(c);
const cooling = []; let head = 0, time = 0;
while (heap.size > 0 || head < cooling.length) {
time++;
if (heap.size > 0) {
const remaining = heap.pop() - 1;
if (remaining > 0) cooling.push({ count: remaining, readyAt: time + n });
}
if (head < cooling.length && cooling[head].readyAt === time) heap.push(cooling[head++].count);
}
return time;
}
console.log('broken heap on the sample:', leastIntervalBrokenHeap(['A','A','A','B','B','B'], 2));
let brokenWrong = 0, firstBreak = null;
for (let total = 1; total <= 10; total++)
for (const shape of countShapes(total, total))
for (let n = 0; n <= 10; n++) {
const tasks = shapeToTasks(shape);
const got = leastIntervalBrokenHeap(tasks, n);
const want = leastIntervalFormula(tasks, n);
if (got !== want) {
brokenWrong++;
if (!firstBreak) firstBreak = { shape, n, got, want };
}
}
console.log('broken heap wrong on', brokenWrong, 'inputs; first:', JSON.stringify(firstBreak));broken heap on the sample: 8
broken heap wrong on 31 inputs; first: {"shape":[2,2,2,1,1],"n":4,"got":9,"want":8}Eight on the sample. Correct, and meaningless — ["A","A","A","B","B","B"] has two distinct tasks,
so the heap never holds more than two elements and there is no right child to ignore. The first
input that catches it needs five distinct tasks. A heap bug hides behind any test whose alphabet is
small.
What the simulation costs
The complexity line people recite for the heap version is O(N log 26), effectively linear. It is
not. The loop body runs once per tick, and it ticks through idle slots one at a time:
const long = [];
for (let i = 0; i < 10000; i++) long.push(i % 2 === 0 ? 'A' : 'B');
console.log('tasks', long.length, 'ticks', leastIntervalHeap(long, 100));tasks 10000 ticks 504901Fifty ticks of loop for every task. The simulation is O((maxFreq - 1) * (n + 1)), which is the
same term that makes the naive scan expensive — the heap fixed which task to pick, not how many
ticks there are. Under LeetCode's constraints (n at most 100) that ceiling is survivable, but it
is the reason the formula exists. The formula is O(N) because it never looks at time at all.
The tradeoff runs the other way too: the simulation can hand you the actual schedule string, and the
formula cannot. Reorganize String (LC 767, n = 1) and Rearrange String k Distance Apart (LC 358,
n = k - 1) both want the string, so both want the heap.
One input separates them
There is one input in the whole space that separates the two implementations, and it is the input the guard I flagged at the top exists to catch.
Write the formula the way almost every published solution writes it — a 26-slot bucket array
instead of a Map:
function leastIntervalBuckets(tasks, n) {
const counts = new Array(26).fill(0);
for (const t of tasks) counts[t.charCodeAt(0) - 65]++;
const maxFreq = Math.max(...counts);
let maxFreqCount = 0;
for (const c of counts) if (c === maxFreq) maxFreqCount++;
return Math.max((maxFreq - 1) * (n + 1) + maxFreqCount, tasks.length);
}
for (const n of [0, 5, 24, 25, 40]) {
console.log(`[] n=${n} -> buckets ${leastIntervalBuckets([], n)}, heap ${leastIntervalHeap([], n)}`);
}[] n=0 -> buckets 25, heap 0
[] n=5 -> buckets 20, heap 0
[] n=24 -> buckets 1, heap 0
[] n=25 -> buckets 0, heap 0
[] n=40 -> buckets 0, heap 0Empty input. maxFreq is 0, so every bucket equals maxFreq, so maxFreqCount is 26, and the
skeleton evaluates to (0 - 1) * (n + 1) + 26, which is 25 - n. The Math.max against
tasks.length cannot save it, because tasks.length is 0 and the wrong value is larger. It takes
n >= 25 for the arithmetic to bury the bug under its own negative term.
Re-running the full sweep with the bucket version in place of the Map version gives 25
disagreements out of 20,828 — one for each n from 0 to 24, all on the empty array, nothing else.
Twenty-five out of twenty thousand is exactly the density at which a sample-based test finds
nothing and a two-implementation sweep finds everything.
LeetCode's constraints say 1 <= tasks.length, so the empty case never fails there. That is why the
bug survives in so many published solutions, and why it will still be sitting in your utility
function the day someone calls it with a filtered-to-empty array.
The Map version is immune for a boring structural reason: it only ever holds keys for tasks that
actually appeared, so an absent task cannot tie for the maximum. The bucket array manufactures 26
zero-count tasks and then lets them win.
Two implementations that must agree will find that in 301 milliseconds. Reading the formula harder will not.
Comments (0)
No comments yet. Be the first to share your thoughts!
Related Articles
