Problem overview
A CPU has a list of tasks, each an uppercase letter from A to Z; equal letters are copies of the same task. Running a task takes one unit of time, and in each unit the CPU runs one task or stays idle. There is a cooldown n: two copies of the same task must be at least n units apart, so after running a task the CPU needs n other units, whether tasks or idle time, before it can run that task again. The tasks can run in any order.
The method leastInterval(tasks, n) returns the fewest units of time needed to run all of them.
For ["A","A","A","B","B","B"] with n = 2 the answer is 8: A B idle A B idle A B. With only two kinds of task, the CPU has to idle twice. With n = 0 there is no cooldown, any order works, and the answer is 6. For six As plus one each of B, C, D, E, F, G, with n = 2, the answer is 16: A B C A D E A F G A idle idle A idle idle A.
The budget is O(T log 26) time, where T is the number of tasks, and O(1) extra space: at most 26 counts.
Approach: always run the task with the most copies left
Only how many copies each task has matters, not which letter it is. So the first step is to count them: 26 counters, one per letter.
The idle time comes from tasks that have to wait. The task with the most copies left needs the most room between its copies, so it should run as early as possible; otherwise its long chain of cooldowns ends up alone at the end, full of idle units. The lesson therefore simulates the CPU with a max-heap of counts (a structure whose top is always the biggest value). In each unit, it runs the task with the most copies left. Then the task waits in a queue until its cooldown is over, and goes back into the heap.
The queue is a plain array of entries [left, readyTime]: the copies the task has left and the time unit at whose end its cooldown is over, so it can run again one unit later. Tasks enter the queue in the order they run, so they also leave it in order of ready time, and the front is always the next one to become ready.
When the heap is empty but tasks are still cooling, the CPU idles. Rather than looping once per idle unit, the simulation sets the time directly to the moment the first waiting task is ready. That jump counts all the idle units in between at once.
The lesson provides a ready-to-use MaxHeap of numbers with insert(value), extract(), size() and isEmpty().
Step by step
- Count the tasks in
count, 26 zeros made withnew Array(26).fill(0): index 0 forA, up to 25 forZ. - Loop over
taskswithfor...ofand add one tocount[task.charCodeAt(0) - 65].charCodeAt(0)is the letter's code and 65 is the code ofA. - Create the heap with
new MaxHeap()and insert every count that is bigger than 0. Letters that never appear have nothing to run. - Create the waiting queue
cooling, an emptynumber[][], and a countertimethat starts at 0. - Simulate with a
whileloop that runs while the heap is not empty orcoolingstill holds a task. The work is done only when no task is waiting to run and none is cooling. - Start a unit:
time++. - If the heap is empty, nothing can run now, so jump:
time = cooling[0][1]. - Otherwise run a task:
heap.extract()gives the biggest count, and subtracting one gives the copiesleftafter this run. - If copies are left, push
[left, time + n]ontocooling. A task run attimecan run again attime + n + 1, afternother units. A task with no copies left is finished and isn't queued. - Release a ready task: if
coolingis not empty and its front entry has a ready time equal totime, remove it withshift()and insert its count back into the heap. - Return
time: the unit in which the last task ran.
The solution in TypeScript
class Solution {
leastInterval(tasks: string[], n: number): number {
const count: number[] = new Array(26).fill(0);
for (const task of tasks) {
count[task.charCodeAt(0) - 65]++;
}
const heap = new MaxHeap();
for (const c of count) {
if (c > 0) {
heap.insert(c);
}
}
const cooling: number[][] = [];
let time = 0;
while (!heap.isEmpty() || cooling.length > 0) {
time++;
if (heap.isEmpty()) {
time = cooling[0][1];
} else {
const left = heap.extract() - 1;
if (left > 0) {
cooling.push([left, time + n]);
}
}
if (cooling.length > 0 && cooling[0][1] === time) {
heap.insert(cooling.shift()[0]);
}
}
return time;
}
}
TypeScript details worth knowing
Letters to indexes. A string is not a number, so task - 65 would not work. task.charCodeAt(0) returns the numeric code of the first character, and subtracting 65 maps A to 0 and Z to 25.
count[...]++ increases the element in place. The array starts with 26 zeros, so no element is ever undefined.
shift() removes and returns the first element of an array. It has to move the other elements, so it is not constant time in general, but cooling never holds more than 26 entries, so it stays cheap.
Entries are arrays. Each queue entry is a two-element number[]. cooling.shift()[0] takes the first element of the removed entry, the count of copies left. The type annotations are erased when the code is compiled to JavaScript, so they have no effect at run time.
No integer type. time is a number and never overflows for the sizes here; its largest value is far below the point where doubles lose precision.
Tracing the simulation
For ["A","A","A","B","B","B"] with n = 2, the counts are 3 and 3. Each row shows the state at the end of one turn of the loop:
| time | what happens | cooling after the turn |
|---|---|---|
| 1 | run a task with 3 copies, 2 left | [[2, 3]] |
| 2 | run the other, 2 left | [[2, 3], [2, 4]] |
| 3 | heap empty: idle; the first task is ready at 3 and returns to the heap | [[2, 4]] |
| 4 | run it, 1 left; the second task is ready and returns | [[1, 6]] |
| 5 | run it, 1 left | [[1, 6], [1, 7]] |
| 6 | heap empty: idle; the first task returns | [[1, 7]] |
| 7 | run it, none left; the second task returns | [] |
| 8 | run it, none left | [] |
The loop ends with time equal to 8. When the heap is empty, the jump time = cooling[0][1] can skip several units at once: for ["A","A"] with n = 3, the first A runs at time 1 and must wait until time 4, so the loop jumps straight there and the answer is 5.
Complexity
Time: O(T log 26). Counting takes O(T). Every task is extracted and inserted again a number of times equal to its copies, so the total number of heap operations is proportional to T, and each costs O(log 26) because the heap never holds more than 26 counts. The jumps make idle units free, so the loop doesn't run once per idle unit, even with a large n.
Space: O(1). The counts, the heap and the queue each hold at most 26 values.
Edge cases and common mistakes
- No cooldown. With
n = 0the answer is just the number of tasks, since every task is ready again at once. - One task.
["A"]withn = 100gives 1: there is no second copy to wait for. - Few kinds, long cooldown.
["A","A"]withn = 3gives 5, and["A","B","C"]withn = 5gives 3, since different tasks don't wait for each other. - Off by one on the cooldown. Two copies of a task must have
nunits between them, so the second can run attime + n + 1. The queue storestime + nas the unit at whose end the wait is over. - Using the smallest count first. Running the task with the fewest copies leaves the long chain for the end and adds idle units.
- Forgetting to check the queue in the loop condition. If the loop stopped when the heap was empty, tasks still cooling would never run.
Testing
The lesson's code gives these results:
leastInterval(["A","A","A","B","B","B"], 2) -> 8
leastInterval(["A","A","A","B","B","B"], 0) -> 6
leastInterval(["A","A","A","A","A","A","B","C","D","E","F","G"], 2) -> 16
leastInterval(["A"], 100) -> 1
leastInterval(["A","A"], 3) -> 5
leastInterval(["A","B","C"], 5) -> 3
