Task Scheduler

Count how many times each task letter occurs, then push the negated counts onto a max-heap. At every time tick, pop the task with the highest remaining count and run it (decrementing its count), placing it in a cooldown queue that says “not eligible again until time + n.” If nothing is ready to run, that tick is idle. Repeat until both the heap and the cooldown queue are empty.

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()]
        heapq.heapify(heap)
        time = 0
        cooldown = deque()  # (time_it_becomes_available_again, remaining_count)

        while heap or cooldown:
            time += 1
            if heap:
                remaining = -heapq.heappop(heap) - 1
                if remaining > 0:
                    cooldown.append((time + n, remaining))
            # bring back any task whose cooldown just expired
            if cooldown and cooldown[0][0] == time:
                _, remaining = cooldown.popleft()
                heapq.heappush(heap, -remaining)

        return time

Watch the timeline fill in from left to right: every interval runs the ready task with the most occurrences left, and whenever the heap empties — because both tasks are still cooling down — a rose idle chip appears. That forced idle slot is the cooldown constraint made visible. The trace below runs the exact example tasks = ["A","A","A","B","B","B"], n = 2:

Why the greedy works: running the most frequent remaining task first spreads its repetitions out as early as possible, leaving the most slack for less-frequent tasks to slot into the resulting cooldown gaps. Delaying the most frequent task instead only pushes its own repetitions further out without helping anything else.

Complexity: there are at most 26 distinct task letters, so the heap and cooldown queue never hold more than 26 items — every operation is O(log 26) = O(1). The loop runs once per output interval, so it’s O(total intervals), which is O(n_tasks) in the best case and bounded by the answer itself in general.

The simulation above is really just enforcing a structural fact: let max_count be the highest frequency of any task, and num_max the number of distinct tasks that hit that frequency. Picture laying out max_count - 1 full “chunks,” each of length n + 1 (the most frequent task, plus n cooldown slots to fill with other tasks or idle time), followed by one final chunk containing just the num_max tasks that tied for most frequent (no trailing cooldown needed after the last occurrence).

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)

Worked example: tasks = ["A","A","A","B","B","B"], n = 2. max_count = 3 (both A and B), num_max = 2. Frame length: (3-1) * (2+1) + 2 = 6 + 2 = 8, laid out as A B _ | A B _ | A B — two chunks of A, B, idle (length 3 each) plus a final A, B with no trailing gap, totaling 8. This is the very schedule the simulation trace above produced, chunked the same way into A B idle | A B idle | A B — so the greedy and the formula agree on 8.

Why the max(len(tasks), ...) matters: when there are enough distinct task types to fill every cooldown gap with real work instead of idling (e.g. ["A","C","A","B","D","B"], n = 1), the frame formula can undercount — there’s simply no idle time at all, so the answer is just the number of tasks, 6. The formula only produces idle time when tasks can’t fill every gap; otherwise the true lower bound is just running every task once.

Correctness: the most frequent task(s) are the true bottleneck — everything else can always be interleaved into the gaps they force, or if there is not enough other work to fill a gap, idle time is unavoidable and the formula accounts for exactly that idle time. Any valid schedule must be at least this long, and this layout achieves it, so it’s optimal.

Complexity: one pass to count frequencies, then a constant amount of arithmetic over at most 26 distinct counts → O(n) time, O(1) space (26 possible letters is a constant).