Find the fewest slots to run every task with n idle gaps between repeats. The most frequent task sets a frame; the rest fill its gaps.
▼The problem
LeetCode 621 (Medium). Given CPU tasks (capital letters) and a cooldown n (two runs of the same task need at least n intervals between them), return the minimum number of intervals the CPU needs to finish every task. In each interval it runs one task or stays idle.
Examples: tasks = ["A","A","A","B","B","B"], n = 2 → 8 (A B idle A B idle A B); the same tasks with n = 0 → 6.
The solution
from collections import Counter
def leastInterval(tasks, n):
counts = Counter(tasks)
top = max(counts.values())
ties = sum(c == top for c in counts.values())
frame = (top - 1) * (n + 1) + ties
return max(len(tasks), frame)Transcript
Task Scheduler. A CPU runs one task per interval. Tasks are letters, and the same letter must wait n intervals before running again. The CPU may idle. Find the fewest intervals to finish.
Take three A's and three B's, with n equal to two. A, B, idle, because A is still cooling. A, B, idle, A, B. Eight intervals.
The naive way simulates the clock. Each interval, pop the ready task with the most runs left from a heap, or idle. It pays for every idle tick, one at a time.
Better: the busiest task sets the frame. A runs three times, so make three rows of n plus one slots. Other tasks fill the gaps, one per row, so their copies stay a row apart. B ties A, so it joins the last row. Frame: top count minus one, times n plus one, plus the ties.
If the gaps overflow, say with two C's and two D's, the rows just get wider and nothing idles. Then the answer is the task count. So take the larger.
In code: count each letter. Take the top count and its ties, build the frame, and return the larger of frame and task count.
On the example: top count three, two ties. Two times three, plus two, is eight, more than six tasks. Eight. With n equal to zero, the frame is two plus two, four, so six tasks win.
Counting is one pass over the tasks, with at most twenty six letters. So time is order N, and space is order one.
Count the busiest task, build its frame, and let the rest fill in. That's Task Scheduler.