The problem
A CPU must run a list of tasks (letters). Each takes one time unit. The same task must wait at least n units before running again; the CPU can sit idle. Find the fewest time units to finish all tasks.
Input: tasks = "AAABBB", n = 2 Output: 8 (A B idle A B idle A B)
Picture it
Picture a chef cooking dishes at stations that need n minutes to cool down after use. Each minute, the chef cooks the dish with the most portions left that is ready (a max-heap picks it). A cooked dish rests in a cooling queue until it may be used again. If nothing is ready, the chef waits (an idle minute).
How to recognise it
- You are scheduling items one per time step, and the same kind of item must wait a minimum gap before it may run again.
- You want the fewest total steps, and idle steps are allowed.
- A greedy rule suggests itself: run the kind with the most work left that is currently allowed.
- Counts change after every step, and you repeatedly need the largest available count. That is a job for a heap (a tree stored in a list that hands out its best item in O(log n)), together with a waiting area for items that are cooling down.
- Up to 10^4 tasks and a cooldown up to 100: the answer can be over a million time units, so enumerating schedules is out.
Start with brute force
Try every possible schedule: at each time unit, either idle or run any kind of task that is ready, and keep the shortest schedule that finishes everything.
from collections import Counter
def least_interval_brute(tasks, n):
kinds = sorted(Counter(tasks).items())
start = (tuple(c for _, c in kinds), tuple(0 for _ in kinds))
seen, frontier, t = {start}, [start], 0
while frontier:
nxt = []
for left, wait in frontier:
if sum(left) == 0:
return t
tick = tuple(max(0, w - 1) for w in wait)
options = [(left, tick)] # stay idle
for i, c in enumerate(left):
if c and wait[i] == 0: # this kind is ready now
l2, w2 = list(left), list(tick)
l2[i] -= 1
w2[i] = n
options.append((tuple(l2), tuple(w2)))
for o in options:
if o not in seen:
seen.add(o)
nxt.append(o)
frontier, t = nxt, t + 1
return 0
This breadth-first search over states (counts left, cooldown per kind) is correct, but the number of states grows exponentially with the counts. With 10^4 tasks it is hopeless.
From brute force to the idea
- Find the waste. Most branches are clearly worse: if a task of the most frequent kind is ready, running something rarer first only delays the bottleneck.
- Go greedy. Each time unit, run the ready kind with the most copies left. Keep counts negated in a heap so Python's min-heap acts as a max-heap.
- Park cooling tasks. After running a kind, if copies remain, put
(count left, time + n)in a queue. Thetime + nvalue is when it becomes ready: it ran attime, so unitstime + 1totime + nare the gap. - Release in order. One task runs per unit, so ready times in the queue are increasing; only its front needs checking. At the end of unit
time, if the front is ready, push it back into the heap. - Idle units happen by themselves. If the heap is empty but the queue is not,
timestill advances, which is the idle unit.
This is the key idea: a max-heap of ready counts plus a cooldown queue simulates the greedy schedule.
The key idea
Greedy: always run the most frequent available task; a queue holds tasks in cooldown. (Formula version: (maxCount − 1) × (n + 1) + number of tasks with maxCount.)
Python solution
def least_interval(tasks, n):
heap = [-c for c in Counter(tasks).values()]
heapify(heap)
cooling, time = deque(), 0 # (count left, ready time)
while heap or cooling:
time += 1
if heap:
c = heappop(heap) + 1 # do the most-needed task
if c: cooling.append((c, time + n))
if cooling and cooling[0][1] == time:
heappush(heap, cooling.popleft()[0])
return timeLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter, deque from heapq import heappush, heappop, heapify
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (search all schedules) | Exponential in the number of tasks | Exponential: every distinct state is stored |
| Heap and queue (shown code) | O(T log 26), where T is the answer; at most 26 kinds, so each heap step is tiny. T is at most about (count of the commonest task) × (n + 1) | O(1): at most 26 entries in total |
Edge cases
- n = 0 (
AAABBB): returns 6, with no idle units. - All tasks distinct (
ABC, n = 5): returns 3; nothing ever has to wait. - One kind (
AAA, n = 2): returns 7 (A, idle, idle, A, idle, idle, A). - Empty list: returns 0.
- Example (
AAABBB, n = 2): returns 8. - Largest input: 10^4 copies of
Awith n = 100 gives 1,009,900 loop iterations, still fast. - Imports: needs
heapify,heappop,heappush,Counteranddeque; the snippet omits them. The input is a list of letters.
Common mistakes
- Waiting
n + 1units after the run instead ofn, so tasks cool for one unit too long.AAABBBwith n = 2 then returns 10. - Running the least frequent kind first, which leaves the bottleneck for the end.
- Computing only
(max_count - 1) * (n + 1)and forgetting the tail: every kind tied for the highest count adds one more unit. - Forgetting that the answer can never be below the number of tasks.
Compute the same answer in O(n) with no heap and no simulation. Describe your approach, then write it if you like.
Compare with our answer
The commonest kind (count m) forces a skeleton of m - 1 full blocks of n + 1 units, followed by a last row that holds one copy of every kind tied for count m. Other tasks fit into the idle slots. If there are so many tasks that no idle slots remain, the answer is just the number of tasks.
from collections import Counter
def least_interval_formula(tasks, n):
counts = Counter(tasks)
m = max(counts.values(), default=0)
tied = sum(1 for c in counts.values() if c == m)
return max(len(tasks), (m - 1) * (n + 1) + tied)
For AAABBB with n = 2 it gives max(6, 2 × 3 + 2) = 8. Time O(n) to count, space O(1).
A strong answer mentions: the skeleton built from the commonest task, the extra unit for each kind tied at the maximum, and the max with the task count.
1. A print server must print jobs one per minute, but jobs from the same user may not print within n minutes of each other. You want the shortest total time. Which approach fits best?
Serving the user with the most remaining work first avoids leaving the bottleneck to the end, and the cooldown queue enforces the gap. Arrival order and fixed rotation waste idle minutes, and trying every ordering is exponential.
2. Why is the shown solution fast even when the answer is over a million time units?
There are at most 26 kinds of task, so each unit costs a tiny O(log 26) amount even though the loop counts every unit. It does not skip idle time, and it keeps going while the cooling queue is non-empty.
3. A learner changes time + n to time + n + 1 in the cooling queue. Which input does it still get right?
With all kinds different no task ever enters the cooling queue, so the extra unit does nothing. The other inputs return 10, 7 and 5 instead.
Score 60% or more and the lesson is marked complete.