Problem overview
A CPU must run 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 every unit the CPU either runs one task or stays idle. Two copies of the same task must be at least n units apart: 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 the tasks.
For tasks = ["A","A","A","B","B","B"] and n = 2 the answer is 8. One best order is 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 and the answer is 6. For ["A","A","A","A","A","A","B","C","D","E","F","G"] and n = 2 the answer is 16: the six A's need two units between each pair, the other tasks fill the first gaps, and the CPU idles in the rest.
The statement asks for 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
Which letter a task is doesn't matter, only how many copies of it there are. So the first step is to count the copies of each letter.
Then simulate the CPU one unit at a time with a greedy rule: run the task that has the most copies left. Its copies need the most room between them, so starting them early leaves the fewest idle units at the end. A max-heap of counts gives the biggest count on top.
After a task runs, it can't run again for a while. A second structure holds it during that time: a queue of waiting tasks, each stored as [left, readyTime], where left is the number of copies still to run and readyTime is the time unit at whose end the cooldown is over. A task run at time t can run again at t + n + 1, after n other units, so its ready time is t + n. Tasks join the queue in the order they run, so they leave it in order of ready time: the front is always the first one to become ready.
When the heap is empty but tasks are still cooling down, the CPU idles. Rather than counting idle units one at a time, the simulation jumps straight to the moment the first waiting task is ready.
There is also a counting shortcut: if the most frequent task appears m times and c different tasks appear that often, the answer is the larger of tasks.length and (m - 1) * (n + 1) + c. This lesson builds the simulation, which also shows how the schedule works.
Step by step
- Count the copies. Create
countwithnew Array(26).fill(0): one place per letter, index 0 for A up to 25 for Z. - Loop over
taskswithfor...of. - Add one to the letter's place.
task.charCodeAt(0)gives the letter's code, and 65 is the code of"A", so subtracting 65 gives an index from 0 to 25. - Create the heap: a
MaxHeapfrom the library the lesson provides. It will hold counts, biggest on top. - Loop over
count, taking each count asc. - Insert only positive counts. A letter that never appears has count 0 and nothing to run.
- Create the queue
coolingas an empty array. Each entry will be[left, readyTime]. - Start
timeat 0. It counts the units used so far and ends as the answer. - Loop while work remains: while the heap isn't empty or
coolingholds a task. - Add one to
time. A new unit starts. - If the heap is empty, nothing can run, so the CPU idles. Set
timeto the first waiting task's ready time,cooling[0][1]. That counts all the idle units in between at once. - Otherwise, run the biggest task.
leftisheap.extract() - 1: the copies it still has after this unit. - Queue it if copies remain. If
left > 0, push[left, time + n]ontocooling. A task with no copies left is done and isn't queued. - Release a ready task. If
coolingisn't empty and its front entry's ready time equalstime, remove it withshift()and insert its count, item 0, back into the heap. - Return
time. It is the unit in which the last task ran.
The solution in JavaScript
var algorithms = require('algorithms')
class Solution {
leastInterval(tasks, n) {
let count = new Array(26).fill(0);
for (let task of tasks) {
count[task.charCodeAt(0) - 65]++;
}
let heap = new algorithms.DataStructures.Heap.MaxHeap();
for (let c of count) {
if (c > 0) {
heap.insert(c);
}
}
let cooling = [];
let time = 0;
while (!heap.isEmpty() || cooling.length > 0) {
time++;
if (heap.isEmpty()) {
time = cooling[0][1];
} else {
let 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;
}
}
The JavaScript details worth a closer look:
- The heap library. JavaScript has no built-in heap. The starter code loads one with
require('algorithms'), whoseMaxHeaphasinsert,extract,isEmptyandn. With no compare function it compares numbers, so the biggest count is extracted first. - Letters to indices. A string has no numeric value, so
charCodeAt(0)returns the code of the character at position 0."A".charCodeAt(0)is 65 and"Z".charCodeAt(0) - 65is 25. - The compound update.
count[...]++reads, adds one and writes back, on an array of zeros thatfill(0)prepared. Without thefill, the places would holdundefined, andundefined + 1isNaN. shift()returns the removed entry.cooling.shift()removes the first entry and returns it, and[0]then reads its count. Removing from the front of an array is slower than from the end, butcoolingnever holds more than 26 entries.- Two-level indexing.
cooling[0][1]is the second item, the ready time, of the first entry. ==on numbers. Both sides are numbers, so==behaves like===here.
Tracing tasks = [A, A, A, B, B, B], n = 2
The counts are 3 and 3. Each row shows one pass of the loop: what the CPU did in that unit, the queue afterwards, and how many counts are in the heap.
| time | action | cooling afterwards | heap size |
|---|---|---|---|
| 1 | run, 2 copies left | [[2,3]] | 1 |
| 2 | run, 2 copies left | [[2,3],[2,4]] | 0 |
| 3 | idle (heap empty), ready task with 2 copies returns | [[2,4]] | 1 |
| 4 | run, 1 copy left; ready task with 2 copies returns | [[1,6]] | 1 |
| 5 | run, 1 copy left | [[1,6],[1,7]] | 0 |
| 6 | idle (heap empty), ready task with 1 copy returns | [[1,7]] | 1 |
| 7 | run, 0 copies left; ready task with 1 copy returns | [] | 1 |
| 8 | run, 0 copies left | [] | 0 |
Now the heap and the queue are both empty, the loop ends, and the method returns 8.
Complexity
Time: O(T log 26). Counting the tasks takes O(T). Each task is run once, which costs one extraction from the heap, and a task that still has copies is inserted again later. So there are about T heap operations in total. The heap never holds more than 26 counts, so each operation costs O(log 26). Idle stretches are skipped in one step, so they add no loop passes.
Space: O(1). The array count has 26 places, and the heap and the queue each hold at most 26 entries.
Edge cases and common mistakes
- No cooldown. With
n = 0the answer is just the number of tasks:["A","A","A","B","B","B"]gives 6. A task run at timetis ready att, and the release check at the end of the same loop pass puts it straight back into the heap. - One task.
["A"]withn = 100gives 1: the cooldown matters only between copies. - A task and its copy.
["A","A"]withn = 3gives 5: A, three idle units, A. - Many kinds, no idling.
["A","B","C","D"]withn = 5gives 4. Different tasks never wait for each other. - Enough variety to fill every gap.
["A","A","A","B"]withn = 2gives 7, and["A","A","B","B"]withn = 1gives 4 (no idle unit needed). - Off by one in the ready time. A task run at
timecan run again attime + n + 1. The queue storestime + n, the unit at whose end it is released, so the task is back in the heap before unittime + n + 1starts. - Counting idle units one by one. This also works but costs a loop pass per idle unit. The jump to
cooling[0][1]skips them all.
Testing
["A","A","A","B","B","B"],n = 2gives8.["A","A","A","B","B","B"],n = 0gives6.["A","A","A","A","A","A","B","C","D","E","F","G"],n = 2gives16.["A"],n = 100gives1.["A","A"],n = 3gives5.["A","A","A","B"],n = 2gives7.
