Each task takes one unit of time. The same task cannot run again until n units have passed. Different tasks have no restriction. The CPU may idle. Return the minimum total time to run everything.
tasks = ["A","A","A","B","B","B"], n = 2 → 8 A B idle A B idle A Btasks = ["A","A","A","B","B","B"], n = 0 → 6
Idle time only happens when every task that is still waiting to run is cooling down. So the real question is: in what order should the tasks run, so that the CPU is idle as little as possible?
Try every possible order of the tasks and keep the shortest valid schedule. With 10,000 tasks that is far beyond any computer. Even a careful search that tries each allowed task at each step branches at every step.
The waste in one sentence: it tries orders that are obviously worse, when a simple rule, "run the most common task that is allowed right now", is always at least as good.
The greedy rule is: at every step, run the most frequent task that is currently allowed.
Why the most frequent? Because it is the one most likely to cause idling later. Spending its copies early spreads them out; leaving them until the end forces gaps you cannot fill.
That needs "the currently largest count", repeatedly, from a changing collection — which is a max-heap. Plus a queue holding tasks that are cooling down and cannot yet be chosen.
import heapqfrom collections import Counter, dequeclass Solution: def leastInterval(self, tasks: List[str], n: int) -> int: counts = Counter(tasks) # (1) heap = [-c for c in counts.values()] # (2) max-heap by negation heapq.heapify(heap) cooling = deque() # (3) (remaining count, time it becomes available) time = 0 # (4) while heap or cooling: # (5) time += 1 # (6) if heap: # (7) remaining = heapq.heappop(heap) + 1 # (8) one copy used (negated) if remaining: # (9) still copies left cooling.append((remaining, time + n)) # else: the CPU idles this tick if cooling and cooling[0][1] == time: # (10) heapq.heappush(heap, cooling.popleft()[0]) return time # (11)
ts
function leastInterval(tasks: string[], n: number): number { const counts = new Map<string, number>(); // (1) for (const t of tasks) counts.set(t, (counts.get(t) ?? 0) + 1); const heap = new MaxHeap<number>(); // (2) for (const c of counts.values()) heap.push(c); const cooling: Array<[number, number]> = []; // (3) let time = 0; // (4) while (heap.size || cooling.length) { // (5) time++; // (6) if (heap.size) { // (7) const remaining = heap.pop()! - 1; // (8) if (remaining > 0) cooling.push([remaining, time + n]); // (9) } if (cooling.length && cooling[0][1] === time) { // (10) heap.push(cooling.shift()![0]); } } return time; // (11)}
(1) Count how many copies of each task there are. The task names do not matter, only the counts.
(2) A heap of counts, biggest first. Python's heap keeps the smallest at the front, so we store negative counts. The most copies becomes the most negative number, which sits at the front. In TypeScript, MaxHeap is the heap from 4.16 with the comparison flipped.
(3) A queue of tasks that are cooling down. Each entry is "how many copies are left" and "the time at which this task may run again".
(4) The clock starts at 0.
(5) Keep going while any task still has copies left, either ready in the heap or waiting in the queue.
(6) One unit of time passes. This happens every turn, whether or not a task runs, which is how idle time gets counted.
(7) If any task is ready, run one.
(8) Take the task with the most copies left, and use one copy. The stored count is negative, so adding 1 moves it one step toward zero, which means one fewer copy.
(9) If copies are left, the task starts cooling. It may run again at time + n. If no copies are left, the task is finished and simply disappears.
(10) A task whose cooldown ends now becomes ready again. Tasks enter the queue in time order, so only the front of the queue can be ready. No second heap is needed.
(11) The clock now shows the total time, including idle units.
, so heappop gives the largest and + 1 decrements it (adding 1 to a negative number moves it towards zero).
The queue is naturally ordered by availability time, because tasks enter it in increasing time order. So only the front ever needs checking — no second heap is required.
When the heap is empty but the queue is not, the CPU idles. The time += 1 happens unconditionally at the top, which is what counts the idle tick.
Time Complexity: Constructing the initial frequencies takes O(N) where N is the number of tasks. The heap contains at most 26 elements (the English alphabet). Each heappop and heappush takes O(\log 26) time, which is practically O(1). Since each task is pushed and popped a number of times proportional to its count, the loop runs O(N) times. Thus, the total time is O(N).
Space Complexity: The counts map, heap, and cooling queue all store at most 26 elements. So the space complexity is strictly O(1) (or O(26)).
And then the catch. If there are plenty of other tasks, they fill every gap and the answer is simply len(tasks) — no idling at all. The formula can even come out smaller than the number of tasks in that case, which would be nonsense.
So take the larger of the two:
python
class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: counts = Counter(tasks) # (12) max_count = max(counts.values()) # (13) num_max = sum(1 for c in counts.values() if c == max_count) # (14) return max(len(tasks), (max_count - 1) * (n + 1) + num_max) # (15)
O(\text{total tasks}) time, O(1) space.
Line by line.(12) Count each task. (13) The highest count, maxCount. (14) How many different tasks share that highest count, numMax. (15) The skeleton length from the formula, or the number of tasks if that is larger, because the CPU can never finish faster than one task per unit of time.
["A","A","A","B","B","B"], n = 2. max_count = 3, num_max = 2 (both A and B).
Formula: (3−1) × (2+1) + 2 = 6 + 2 = 8. Task count is 6. Take the max → 8 ✓.
With n = 0: (3−1) × 1 + 2 = 4. Task count is 6. Take the max → 6 ✓. Here the len(tasks) term is what saves it, because with no cooldown there is never any idling.
The formula is shorter and faster. The simulation is easier to trust and it generalises — if the problem later asks which task runs at each moment, or gives tasks different durations, the formula collapses and the heap still works.
Say the greedy rule, describe the simulation, then offer the formula with its derivation. That order shows you understand why the formula is true rather than having memorised it.
Reorganize String — rearrange a string so no two neighbours match. Same greedy rule with n = 1, and it is impossible exactly when maxCount > (len+1)/2, which is this formula in disguise.
Rearrange String k Distance Apart — the same with a general gap.
Real scheduling — rate limiting, retry backoff, and job schedulers all face "run the most urgent thing that is currently allowed". Chapter 11.18 builds a job scheduler properly.
"Why run the most frequent task first?" It is the one that will cause idling later, so its copies must be spread out early.
"Derive the formula." Skeleton of maxCount − 1 gaps of width n, plus the last block containing every task tied at the maximum.
"Why the max with len(tasks)?" When there are enough other tasks to fill every gap, there is no idling and the answer is just the task count.
"What if tasks had different durations?" The formula breaks; the heap simulation still works. This is the question that rewards having both.
One thing to volunteer: draw the skeleton A _ _ A _ _ A before writing the formula. Every term becomes visible from the picture, and it is far more convincing than the algebra alone.