Task Scheduler

Problem

You are given a list of CPU tasks, each labeled with an uppercase letter A–Z, and a non-negative integer n (the cooldown). The CPU works in discrete time intervals: in each interval it either executes exactly one task or sits idle.

Two executions of the same task label must be separated by at least n intervals: after running task X, the CPU must wait at least n other intervals (running different tasks or idling) before it can run X again. Tasks may be executed in any order.

Return the minimum total number of intervals (work + idle) required to finish every task.

Examples

• tasks = ["A","A","A","B","B","B"], n = 2 → 8 One optimal schedule is A B idle A B idle A B: each pair of same letters is 3 slots apart, satisfying the cooldown of 2.
• tasks = ["A","C","A","B","D","B"], n = 1 → 6 With cooldown 1, alternate letters like A B A B C D — no idle intervals are ever needed.
• tasks = ["A","A","A","B","B","B"], n = 3 → 10 A B idle idle A B idle idle A B: the two most frequent tasks can’t fill the wide gaps, so the CPU idles.

Constraints

• 1 <= tasks.length <= 10^4
• tasks[i] is an uppercase English letter (at most 26 distinct labels)
• 0 <= n <= 100

Think about it first

TL;DR

Greedy counting formula (or max-heap + cooldown queue): O(T) time, O(1) space (26 letters).

Approach 1 — Brute force: tick-by-tick simulation

Simulate the clock one interval at a time. At each tick, scan all 26 letters, find the ones whose last execution was more than n ticks ago, and run the one with the most remaining copies. Running the most frequent task first is the correct greedy choice: it spreads out the letters that are hardest to separate. If nothing is runnable, idle.

from collections import Counter


def leastInterval(tasks: list[str], n: int) -> int:
    remaining = Counter(tasks)
    last_run = {t: -(n + 1) for t in remaining}  # "never run"
    time = 0
    done = 0
    total = len(tasks)
    while done < total:
        best = None
        for t, cnt in remaining.items():
            if cnt > 0 and time - last_run[t] > n:
                if best is None or cnt > remaining[best]:
                    best = t
        if best is not None:
            remaining[best] -= 1
            last_run[best] = time
            done += 1
        time += 1
    return time

Complexity: the answer can be as large as T + (f - 1) * n ≈ 10^4 * 100 = 10^6 intervals, and each tick scans 26 letters — O(answer × 26) time, O(1) space.

With up to a million ticks and a linear scan per tick, this is far more work than needed. The better approach computes the schedule length directly instead of stepping through it.

Approach 2 — Max-heap + cooldown queue

Only the count of remaining copies matters, not which letter a task is. Keep a max-heap of remaining counts (Python’s heapq is a min-heap with O(log n) push/pop, so store negated counts). When a task runs, it enters a FIFO cooldown queue stamped with the tick at which it becomes available again. Because tasks enter the queue in tick order, it stays sorted by ready time, so only its head ever needs checking.

flowchart LR
    H[Max-heap: ready task counts] -->|pop most frequent, run one copy| R[Run task]
    R -->|copies remain| Q[Cooldown queue: ready at time + n + 1]
    Q -->|ready tick reached| H
    R -->|no copies left| D[Done]

import heapq
from collections import Counter, deque


def leastInterval(tasks: list[str], n: int) -> int:
    counts = Counter(tasks)
    heap = [-c for c in counts.values()]  # max-heap via negation
    heapq.heapify(heap)
    cooldown: deque[tuple[int, int]] = deque()  # (ready_tick, neg_count)
    time = 0
    while heap or cooldown:
        time += 1
        if cooldown and cooldown[0][0] == time:
            ready = cooldown.popleft()
            heapq.heappush(heap, ready[1])
        if heap:
            neg = heapq.heappop(heap) + 1  # ran one copy
            if neg < 0:  # copies remain -> start cooling down
                cooldown.append((time + n + 1, neg))
    return time

Walkthrough of tasks = ["A","A","A","B","B","B"], n = 2 (heap holds -3, -3):

Both containers empty, so return 8.

Complexity: each of the ≤ T executions does O(log 26) heap work, plus idle ticks — O(T + T·n) in the worst case; space O(1) (at most 26 entries).

Approach 3 — Greedy counting formula

The most frequent task (count f) dictates the schedule’s skeleton. Lay out its f copies; between consecutive copies there must be n other slots, giving (f - 1) blocks of width (n + 1) plus the final copies. Every task tied at count f adds one slot to the tail. All less-frequent tasks fit into the gaps without stretching the schedule: they round-robin across the f - 1 gaps, and extra columns only widen blocks, never violating cooldown. When tasks are plentiful enough that no idling is ever needed, the answer is len(tasks), which is why the formula takes the max.

from collections import Counter


def leastInterval(tasks: list[str], n: int) -> int:
    counts = Counter(tasks).values()
    max_count = max(counts)
    num_max = sum(1 for c in counts if c == max_count)
    return max(len(tasks), (max_count - 1) * (n + 1) + num_max)

Walkthrough of tasks = ["A","A","A","B","B","B"], n = 2: max_count = 3 (A and B tied, so num_max = 2). Skeleton: (3 - 1) * (2 + 1) + 2 = 8. Since 8 > len(tasks) = 6, answer 8 — exactly the A B idle A B idle A B layout. For the second example (n = 1, six distinct-ish tasks, max_count = 2, num_max = 2): formula gives (2-1)*2 + 2 = 4, but len(tasks) = 6 wins → 6, no idles.

Complexity: O(T) time to count, O(1) space.

Common pitfalls

• Forgetting the max(len(tasks), …) clamp in the formula — when tasks are plentiful and varied, the skeleton estimate undershoots the trivial lower bound of one interval per task.
• Counting num_max as 1 instead of counting all letters tied at the maximum frequency — the tail of the schedule holds one slot per tied letter.
• In the heap simulation, re-queuing a task with a ready time of time + n instead of time + n + 1 (the gap must contain n other intervals, so the next run is n + 1 ticks later).
• Popping several heap items per tick — exactly one task runs per interval; batch-popping breaks the cooldown bookkeeping.

Pattern takeaway

When a greedy repeatedly needs the current best among a changing set, a heap makes each selection cheap — here, “most copies remaining” under a cooldown constraint. Once the structure of the greedy is fully understood, the heap can sometimes be replaced by direct arithmetic. The progression from simulation to heap to closed-form formula is a useful pattern for scheduling problems.