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.

The catch: two executions of the same task label must be separated by at least n intervals. In other words, 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

The naive idea: 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 first is the intuitive greedy — it spreads out the letters that are hardest to separate). If nothing is runnable, idle.

from collections import Counter


class Solution:
    def leastInterval(self, 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.

Millions of ticks with a linear scan per tick is pure busywork; the constraints reward computing the schedule length, not living through it.

Approach 2 — Max-heap + cooldown queue

The insight: we never care which letter a task is, only how many copies remain. Keep a max-heap of remaining counts (Python’s heapq is a min-heap, the classic binary-heap structure with O(log n) push/pop, so we store negated counts). When a task runs, it goes into a FIFO cooldown queue stamped with the tick at which it becomes available again; the queue is naturally sorted by ready time, so only its head ever needs checking.

import heapq
from collections import Counter, deque


class Solution:
    def leastInterval(self, 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 → return 8. ✓

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

Approach 3 — Greedy counting formula

The insight: 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 can be round-robined across the f - 1 gaps, and extra columns just widen blocks, never violating cooldown). If there are so many tasks that no idling is ever needed, the answer is simply len(tasks) — hence the max.

from collections import Counter


class Solution:
    def leastInterval(self, 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 needs “the current best among things that keep changing,” a heap is the data structure that makes the greedy cheap — here, “most copies remaining” under a cooldown constraint. And once the greedy’s structure is understood well enough, the heap can sometimes be compiled away into pure arithmetic: simulation → heap → formula is a ladder worth climbing on any scheduling problem.