Problem overview
leastInterval receives tasks, an array of uppercase letters (a [Character]), and a cooldown n. 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, tasks or idle, before it can run that letter again. The tasks can run in any order. The function returns the fewest units needed to run all of them.
For ["A", "A", "A", "B", "B", "B"] with 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, any order works, and the answer is 6. For six A's and one each of B to G with n = 2 the answer is 16: the six A's need two units between each other, the other tasks fill the first gaps, and the CPU idles in the rest.
The task asks for O(T log 26) time, where T is the number of tasks, and O(1) extra space. The log 26 is there because the heap never holds more than 26 kinds of task.
Approach: always run the task with the most copies left
Only how many copies each task has matters, not the letters. So start by counting the copies of each letter.
Then simulate the CPU with a max-heap of counts. In each unit, run the task with the most copies left. Those copies need the most room between them, so starting them early leaves the fewest idle units at the end. After a task runs, it can't run again for n units, so it waits in a queue, cooling, together with the moment its cooldown is over. When that moment comes, the task goes back into the heap with its remaining count.
Tasks join the queue in the order they run, so they also leave it in order of ready time. The task at the front is always the first one ready, and a plain array used as a queue is enough.
When the heap is empty but tasks are still cooling, the CPU can't run anything. Instead of idling one unit per turn, the code jumps time straight to the moment the first waiting task is ready. That counts all the idle units in between at once.
There is also a counting shortcut: if the most frequent task appears m times and c tasks appear that often, the answer is the bigger of tasks.count and (m - 1) * (n + 1) + c. This lesson practises the heap simulation.
Step by step
- Create the counts:
var count = [Int](repeating: 0, count: 26), one place per letter, index 0 for A up to 25 for Z. - Loop over the tasks with
for task in tasks. - Count each letter: add one at index
Int(task.asciiValue!) - 65. The ASCII code ofAis 65, so A goes to index 0. - Create the heap:
var heap = MaxHeap(). The lesson provides aMaxHeapofIntwithinsert(value),extract(),countandisEmpty. The biggest count is on top. - Loop over
countwithfor c in count. - Insert the non-zero counts: if
c > 0, insertc. Letters that never appear have nothing to run. - Create the queue:
var cooling = [(Int, Int)](). Each entry is(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. - Start the clock:
var time = 0. It counts the units used so far and is the answer at the end. - Loop while work remains:
while !heap.isEmpty || !cooling.isEmpty. The work is done only when nothing waits to run and nothing is cooling down. - Start a new unit:
time += 1. - Nothing ready: if
heap.isEmpty, settimetocooling[0].1, the ready time of the first waiting task. - Otherwise run a task: in the
elsebranch,let left = heap.extract() - 1. Running the task uses up one copy. - Queue it if copies remain: if
left > 0, append(left, time + n)tocooling. A task run attimecan run again attime + n + 1, afternother units. Finished tasks aren't queued. - Release a cooled task: still inside the loop, if
!cooling.isEmpty && cooling[0].1 == time, remove the front withcooling.removeFirst()and insert its count,.0, back into the heap. The queue never holds more than 26 tasks, so removing from its front stays quick. - Return
time, the unit in which the last task ran.
The solution in Swift
class Solution {
func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
var count = [Int](repeating: 0, count: 26)
for task in tasks {
count[Int(task.asciiValue!) - 65] += 1
}
var heap = MaxHeap()
for c in count {
if c > 0 {
heap.insert(c)
}
}
var cooling = [(Int, Int)]()
var time = 0
while !heap.isEmpty || !cooling.isEmpty {
time += 1
if heap.isEmpty {
time = cooling[0].1
} else {
let left = heap.extract() - 1
if left > 0 {
cooling.append((left, time + n))
}
}
if !cooling.isEmpty && cooling[0].1 == time {
heap.insert(cooling.removeFirst().0)
}
}
return time
}
}
Swift details worth knowing:
Character.asciiValueis an optionalUInt8: it isnilfor characters outside ASCII. Every task is a letter, so!unwraps it safely, andInt(...)converts it to anIntbefore subtracting 65. For"Z"the value is 90, which gives index 25.- Tuples as queue entries.
(left, time + n)is a pair ofInts, read back with.0and.1. The array type[(Int, Int)]holds such pairs. removeFirst()removes and returns the first element, here the whole tuple, and.0takes its count. It shifts the remaining elements, which is cheap for a queue of at most 26 entries.- Short-circuit
&&. In!cooling.isEmpty && cooling[0].1 == time, the second part is only evaluated when the queue has an element, socooling[0]never reads an empty array. - The jump. After
time += 1, the assignmenttime = cooling[0].1replaces the new value. This is safe because the front of the queue is always at the current time or later.
Complexity
Time: O(T log 26). Counting is O(T). Each task copy is extracted from the heap once and inserted back at most once per run, and the heap holds at most 26 counts, so each operation costs O(log 26). Idle stretches are skipped in one jump, so the loop turns once per task run.
Space: O(1). The count array has 26 places, the heap at most 26 entries, and the queue at most 26 tuples.
Edge cases and common mistakes
- No cooldown. With
n = 0, a task goes intocoolingwith ready time equal to the currenttime, and it returns to the heap in the same unit. The answer is just the number of tasks: 6 for A A A B B B. - A single task kind.
["A"]withn = 5gives 1: the cooldown only applies between copies.["A", "A"]withn = 3gives 5: A, three idle units, A. - Enough other tasks.
["A", "A", "B"]withn = 2gives 4 (A B idle A), and["A", "B", "C", "D"]withn = 4gives 4: no cooldown ever matters because no letter repeats. - Large cooldown.
["A", "A", "B", "B"]withn = 100gives 103: A B, then 99 idle units, then A B. - Running the smallest count first. The heap must hand out the biggest count. A smaller count first can leave one frequent task alone at the end with many idle units between its copies.
- Off-by-one on the ready time. The entry stores
time + n, the unit at whose end the cooldown is over. The task can run again one unit later, attime + n + 1. - Forgetting the empty-heap case. If the loop only ran tasks, a heap that is empty while tasks are still cooling leaves nothing to extract, and the simulation can't move on.
Testing
["A", "A", "A", "B", "B", "B"],n = 2gives 8.["A", "A", "A", "B", "B", "B"],n = 0gives 6.- Six A's plus B, C, D, E, F, G with
n = 2gives 16. ["A"],n = 5gives 1.["A", "A", "B"],n = 2gives 4, and["A", "A", "A", "B"]withn = 3gives 9.
On the first example the simulation runs one task at times 1 and 2, then reaches time 3 with an empty heap: the CPU is idle in that unit, and the first waiting task becomes ready at its end. It runs two more at times 4 and 5, has another idle unit at time 6, and finishes at times 7 and 8.
