Problem overview
The method leastInterval receives tasks, a list of uppercase letters, and a cooldown n. Equal letters are copies of the same task. Running a task takes one unit of time, and in each 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, which can be other tasks or idle time, before it runs that task again. The tasks can run in any order.
The method returns the fewest units of time needed to run everything.
For tasks = ["A", "A", "A", "B", "B", "B"] and 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 ["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 them, the other tasks fill the first gaps, and the CPU idles in the rest.
Approach: always run the task with the most copies left
Only the number of copies of each task matters, not what the tasks are called. So the first step is to count them.
Then simulate the CPU one unit at a time. In every unit, run the task with the most copies left. Tasks with many copies need the most room between their runs, so starting them early leaves the fewest idle units at the end. After a task runs, it has to wait for its cooldown, so it leaves the pool of ready tasks and waits in a queue. When its cooldown is over, it goes back to the pool with its smaller count.
Two data structures do the work:
- A max-heap of counts for the tasks that can run now. Python's
heapqis a min-heap, so the counts are stored negated, and the most frequent task is on top. There are at most 26 kinds of task, so the heap never holds more than 26 entries, which is wherelog 26in the time comes from. - A queue (
deque) of tasks that are cooling down. Each entry is a tuple(left, readyTime): the copies the task has left, and the time unit at whose end its cooldown is over. Tasks enter in the order they run, so they leave in the order of their ready times, and the front is always the next one ready.
When no task is ready, the CPU idles. Instead of looping once per idle unit, the simulation jumps straight to the moment the first waiting task is ready. That keeps the loop to at most one turn per task run.
Here is the simulation on ["A", "A", "A", "B", "B", "B"] with n = 2:
time 1: run, 2 left
time 2: run, 2 left
idle: time jumps to 3
at end of 3: task with 2 left is ready
time 4: run, 1 left
at end of 4: task with 2 left is ready
time 5: run, 1 left
idle: time jumps to 6
at end of 6: task with 1 left is ready
time 7: run, 0 left
at end of 7: task with 1 left is ready
time 8: run, 0 left
8
The task run at time 1 is ready again at the end of time 3, and the one run at time 2 at the end of time 4. Units 3 and 6 are the two idle units, so the total is 8.
Step by step
- Count the tasks with
count = Counter(tasks).Countermaps each letter to how many times it appears. - Build the heap list.
heapholds every count fromcount.values(), negated, so the biggest count is the smallest value. - Arrange it as a heap with
heapq.heapify(heap). It works in place and returnsNone, so its result isn't assigned. - Create
coolingas an emptydeque(), the queue of waiting tasks. - Start
timeat 0. It counts the units used so far and ends as the answer. - Loop while
heap or coolingholds something. The work is done only when no task is ready and none is cooling down. - Add 1 to
time: a new unit starts. - If the heap is empty, no task can run now. Set
timeto the ready time of the first waiting task,cooling[0][1], which counts every idle unit in between at once. - Otherwise run a task. Pop the top of the heap, negate it back, and subtract 1:
leftis how many copies the task still has. - Queue it if copies remain. If
left > 0, append(left, time + n)tocooling. A task run attimecan run again attime + n + 1, afternother units. Tasks with no copies left are done. - Release a ready task. If
coolingis not empty and its front has ready time equal totime, remove it withpopleft()and push its count, negated, back onto the heap. - Return
time. It is the unit in which the last task ran.
The solution in Python
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
count = Counter(tasks)
heap = [-c for c in count.values()]
heapq.heapify(heap)
cooling = deque()
time = 0
while heap or cooling:
time += 1
if not heap:
time = cooling[0][1]
else:
left = -heapq.heappop(heap) - 1
if left > 0:
cooling.append((left, time + n))
if cooling and cooling[0][1] == time:
heapq.heappush(heap, -cooling.popleft()[0])
return time
Python details worth a closer look:
Counteranddeque. Both come from thecollectionsmodule. In a file of your own, you would addfrom collections import Counter, dequeandimport heapq.- Negative counts. The heap holds values like
-3. Popping gives-3, and-heapq.heappop(heap) - 1turns it into3 - 1 = 2: negate first, then subtract. Writing it as-(heappop(heap) - 1)would give 4 instead. heapifyreturnsNone.heap = heapq.heapify(heap)would replace the list withNone. The call is a statement on its own.- Truthiness of containers.
while heap or coolingandif not heapuse the fact that an empty list or deque counts as false.cooling and cooling[0][1] == timechecks that the queue has an item before reading its front. - A deque for the queue.
appendadds at the back andpopleftremoves from the front, both in constant time. A list'spop(0)shifts every element and would be slower on long queues. - Tuples.
cooling[0][1]is the second item of the front tuple, the ready time.cooling.popleft()[0]removes the front tuple and takes its first item, the number of copies left. - The name
time. It is an ordinary variable here. It would hide thetimemodule if the file imported it, which this solution doesn't.
Complexity
Time: O(T log 26), where T is the number of tasks. Counting takes O(T). Each turn of the loop either runs a task, one per copy, or jumps over idle time, and a jump is always followed by running a task, so there are at most 2T turns. Each turn does a heap operation on at most 26 entries, which costs O(log 26), a constant. The heap and the queue never hold more than 26 kinds of task.
Space: O(1). The counter, the heap and the queue each hold at most 26 entries.
Edge cases and common mistakes
- A single task.
["A"]withn = 5gives 1. The only copy runs, nothing is left, and the cooldown never matters. - No cooldown. With
n = 0a task is queued with ready time equal totime, so it is released at the end of the same unit. The CPU never idles and the answer is the number of tasks. - One frequent task.
["A", "A", "A"]withn = 2gives 7:A idle idle A idle idle A. The idle units are counted by the jumps. - Many kinds of task.
["A", "A", "A", "B", "B", "B", "C", "C", "C"]withn = 2gives 9: no idle time is needed, because the three tasks fill each other's cooldowns. - A very long cooldown.
["A", "A", "B", "B"]withn = 100gives 103. The jumps cross the long idle stretches in a single turn each. - The ready time. A task run at
timecan run again attime + n + 1. That is why the queue storestime + n, the unit at whose end the cooldown is over, and releases the task at the end of that unit. Storingtime + n + 1would release it one unit late. - A counting shortcut. The answer also equals the bigger of
len(tasks)and(m - 1) * (n + 1) + c, wheremis the highest count andcis how many tasks have that count. For the first example that ismax(6, 2 * 3 + 2) = 8. The simulation is the lesson's approach; the formula agrees with it on the examples above.
Testing
tasks = ["A", "A", "A", "B", "B", "B"],n = 2gives8.tasks = ["A", "A", "A", "B", "B", "B"],n = 0gives6.tasks = ["A", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"],n = 2gives16.tasks = ["A"],n = 5gives1.tasks = ["A", "A", "A"],n = 2gives7.tasks = ["A", "A", "A", "B", "B", "B", "C", "C", "C"],n = 2gives9.tasks = ["A", "A", "B", "B"],n = 100gives103.
