220. Task Scheduler with Cooldown

Why this mechanism works

Let f be the largest frequency and c the number of labels occurring f times. The first f-1 occurrences of a most frequent label require frames of at least n+1 slots, followed by a final group of c tied labels. This gives a spacing lower bound. The task count gives another lower bound; other labels either fill the frames or make the schedule longer without idles.

State and boundaries

frequencies records task multiplicities. maximum=f and tied=c determine the unavoidable cooldown frame length.

Protocol

1. Count labels and handle empty input.
2. Find the maximum frequency.
3. Count labels tied at that maximum.
4. Compute (f-1)*(n+1)+c.
5. Return the larger of that bound and the number of tasks.

Visualization

A A A B B B, n=2
one optimum: A B _ A B _ A B
f=3,c=2 -> (3-1)*3+2 = 8 slots

Python implementation

from collections import Counter

def task_scheduler(tasks, n):
    if not tasks:
        return 0
    counts = Counter(tasks)
    maximum = max(counts.values())
    tied = sum(value == maximum for value in counts.values())
    return max(len(tasks), (maximum - 1) * (n + 1) + tied)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 task_scheduler: if not tasks:
tasks=['A', 'A', 'A', 'B', 'B', 'B']; n=2

L6 task_scheduler: counts = Counter(tasks)
tasks=['A', 'A', 'A', 'B', 'B', 'B']; n=2; counts={'A':3, 'B':3}

L7 task_scheduler: maximum = max(counts.values())
tasks=['A', 'A', 'A', 'B', 'B', 'B']; n=2; counts={'A':3, 'B':3}; maximum=3

L8 <genexpr>: tied = sum(value == maximum for value in counts.values())
.0=dict_valueiterator; value=3; maximum=3

L8 <genexpr>: tied = sum(value == maximum for value in counts.values())
.0=dict_valueiterator; value=3; maximum=3

L8 <genexpr>: tied = sum(value == maximum for value in counts.values())
.0=dict_valueiterator; value=3; maximum=3

L8 task_scheduler: tied = sum(value == maximum for value in counts.values())
tasks=['A', 'A', 'A', 'B', 'B', 'B']; n=2; counts={'A':3, 'B':3}; maximum=3; tied=2

L4 task_scheduler: if not tasks:
tasks=['A', 'A', 'A', 'B', 'B', 'B']; n=0

L6 task_scheduler: counts = Counter(tasks)
tasks=['A', 'A', 'A', 'B', 'B', 'B']; n=0; counts={'A':3, 'B':3}

L7 task_scheduler: maximum = max(counts.values())
tasks=['A', 'A', 'A', 'B', 'B', 'B']; n=0; counts={'A':3, 'B':3}; maximum=3

L8 <genexpr>: tied = sum(value == maximum for value in counts.values())
.0=dict_valueiterator; value=3; maximum=3

L8 <genexpr>: tied = sum(value == maximum for value in counts.values())
.0=dict_valueiterator; value=3; maximum=3

L8 <genexpr>: tied = sum(value == maximum for value in counts.values())
.0=dict_valueiterator; value=3; maximum=3

L8 task_scheduler: tied = sum(value == maximum for value in counts.values())
tasks=['A', 'A', 'A', 'B', 'B', 'B']; n=0; counts={'A':3, 'B':3}; maximum=3; tied=2

Why the solution is correct

Any schedule must fit every task and separate repeated maximum-frequency labels, establishing both lower bounds. Arrange maximum-frequency labels in successive frames and distribute lower-frequency labels among the gaps. If enough tasks fill all gaps, task count suffices; otherwise remaining gaps are idle, attaining the frame bound.

Time and space

Expected O(T+U) time and O(U) auxiliary frequency storage for T tasks and U distinct labels.

Common mistakes

Using only one most frequent label undercounts the final tied group. Cooldown n means n intervening slots, so equal-label start positions differ by at least n+1.

Reasoning card

Transfer exercise

Construct a concrete schedule with a max-heap and cooldown queue, and verify its length against this formula.