Task Scheduler

A CPU must run a list of tasks with a rule: the same task type needs a cooldown before it can run again. This problem appears often because it has three good answers, each a step deeper than the last: a simulation, a heap, and a formula.

The problem

You get a list of tasks, each a capital letter, and a cooldown n. Each tick of time, the CPU either runs one task or stays idle. Between two runs of the same letter there must be at least n other ticks, busy or idle. Tasks can run in any order. Return the smallest number of ticks needed to run them all.

• tasks = [A, A, A, B, B, C], n = 2 → 7. One best schedule is A B C A B idle A. Each pair of A's has two ticks between them.
• tasks = [A, A, A, B, B, B, C, C, D, D], n = 2 → 10. There are enough other tasks to fill every gap, so no idle is needed: A B C A B D A B C D.

Constraints: 1 ≤ len(tasks) ≤ 10⁴, 26 possible letters, 0 ≤ n ≤ 100.

Clarifying questions

• Do I return the schedule or only its length? Only the length.
• Is n = 0 possible? Yes; then the answer is simply len(tasks).
• Does the cooldown apply between different letters? No, only between copies of the same letter.

Approach 1: tick-by-tick simulation with a scan

Simulate time. At each tick, look at every task type that is off cooldown, run the one with the most copies left, or idle if none is ready.

1from collections import Counter23def least_interval_simulate(tasks: list[str], n: int) -> int:4    """Tick by tick: run the ready task with the most copies left, else idle."""5    remaining = Counter(tasks)6    ready_at = {task: 0 for task in remaining}   # first tick each task may run7    time = 08    while remaining:9        best = None10        for task, count in remaining.items():11            if ready_at[task] <= time and (best is None or count > remaining[best]):12                best = task13        if best is not None:14            remaining[best] -= 115            ready_at[best] = time + n + 116            if remaining[best] == 0:17                del remaining[best]18        time += 1                                # one tick passes, busy or idle19    return time

Let T be the answer and m the number of task types. Each tick scans all m types, so the time is O(T × m). With only 26 letters that passes. But if task types were unbounded — say 10⁴ distinct job ids — the scan makes it O(T × m) = 10⁸ or more. The scan for "the ready type with the most copies left" is exactly the job a heap does in O(log m).

Why is "most copies left" the right choice? The task with the most copies is the one that forces idle time: its copies must be spread n + 1 apart, and every tick you delay it pushes its last copy later. Running it as soon as it is ready keeps those gaps as short as possible, and any other ready task can fill the gaps later. (The code for this lesson was checked against an exhaustive search of every possible schedule on small inputs, and the greedy always matched.)

The key insight

Two kinds of tasks exist at any moment: those ready to run, and those cooling down. You want the ready task with the largest count — a max-heap of counts. The cooling tasks leave the heap and wait in a queue in the order they ran. Since every task cools for the same n ticks, the queue is already sorted by the time each task becomes ready. Only the front of the queue can come back at any tick.

Then look at the answer from a different angle. The most frequent task, with top copies, fixes the shape of the schedule. Its copies sit at the start of top - 1 frames, each n + 1 ticks wide, plus one final copy:

A _ _ | A _ _ | A          top = 3, n = 2: (3 - 1) frames of 3 ticks, then AA B C | A B _ | A          fill the gaps with the other tasks

Every other task fits into the gaps. If several tasks share the top count, each adds one slot at the end, next to the final A. If there are more tasks than gaps, the frames stretch, no idle is needed, and the answer is simply len(tasks).

Approach 2: a max-heap and a cooldown queue

1import heapq2from collections import Counter, deque34def least_interval_heap(tasks: list[str], n: int) -> int:5    """Max-heap of remaining counts plus a queue of tasks cooling down."""6    heap = [-count for count in Counter(tasks).values()]   # negated: max-heap7    heapq.heapify(heap)8    cooling: deque[tuple[int, int]] = deque()   # (ready_time, -count), in time order9    time = 010    while heap or cooling:11        time += 112        if heap:13            count = heapq.heappop(heap) + 1      # run one copy; count is negated14            if count < 0:                        # copies left: cool down for n ticks15                cooling.append((time + n, count))16        if cooling and cooling[0][0] == time:17            heapq.heappush(heap, cooling.popleft()[1])18    return time

The heap stores only counts, not letters, because the answer does not depend on names. A task that runs at tick t becomes ready again after tick t + n, so it is put back into the heap at the end of tick t + n, ready for tick t + n + 1. If the heap is empty but the queue is not, the tick is idle.

Dry run on [A, A, A, B, B, C], n = 2. Letters are shown to make the table readable; the code sees counts A = 3, B = 2, C = 1.

Seven ticks. Correct.

Complexity. Each tick does O(log m) heap work, and there are T ticks, where T can include idles. So O(T log m) time, O(m) space. With 26 letters, log m is below 5.

Approach 3: the counting formula

1from collections import Counter23def least_interval_formula(tasks: list[str], n: int) -> int:4    """Count the frames built around the most frequent task."""5    counts = Counter(tasks).values()6    top = max(counts)7    tied = sum(1 for c in counts if c == top)   # tasks that share the top count8    framed = (top - 1) * (n + 1) + tied9    return max(framed, len(tasks))

On [A, A, A, B, B, C] with n = 2: top = 3, tied = 1, so framed = 2 × 3 + 1 = 7, and max(7, 6) = 7.

On [A, A, A, B, B, B, C, C, D, D] with n = 2: top = 3, tied = 2 (A and B), framed = 2 × 3 + 2 = 8. But there are 10 tasks, and a schedule can never be shorter than the number of tasks, so the answer is max(8, 10) = 10.

Time O(len(tasks)) for counting, O(1) space since there are at most 26 counts. This is the answer to lead with once you have explained why the frames work — but many interviewers want the heap version first, because it generalises to problems where the formula does not exist (different cooldowns per task, or needing the actual order).

Edge cases

• n = 0: no cooldown. The formula gives (top - 1) × 1 + tied, which is at most len(tasks), so the answer is len(tasks).
• One task type, [A, A, A], n = 2: A idle idle A idle idle A = 7. Formula: 2 × 3 + 1 = 7.
• All tasks distinct: top = 1, framed = tied = m = len(tasks). No idles.
• Many tasks tied at the top: the tied term handles it; forgetting it undercounts by tied - 1.

Follow-ups

• "Return the schedule itself." Use the heap version and store (count, letter) so you know what ran; append idle on empty ticks.
• "Rearrange a string so no two equal letters are adjacent" (Reorganize String). The same heap with n = 1 and no idles allowed; if the heap is empty while a letter is still cooling, return that it is impossible.
• "Tasks must run in the given order, with cooldowns." Now there is no choice to make; use a hash map from task to the last tick it ran and jump time forward. No heap needed.