The problem
A CPU must run a list of tasks, each labelled with a letter A–Z. Every task takes one time unit. Two tasks with the same label must be at least n time units apart; in between, the CPU runs other tasks or sits idle.
Return the least number of time units needed to finish every task.
Examples
- Input
tasks = ["A", "A", "A", "B", "B", "B"], n = 2
- Output
8
- Input
tasks = ["A", "C", "A", "B", "D", "B"], n = 1
- Output
6
- Input
tasks = ["A", "A", "A", "B", "B", "B"], n = 3
- Output
10
Constraints
- 1 ≤ tasks.length ≤ 10⁴
- Each task is an uppercase English letter.
- 0 ≤ n ≤ 100
The idea
The commonest task sets the pace. If it occurs most times, its runs need most − 1 gaps of n between them: picture most − 1 frames of n + 1 slots, each starting with that task, then one final slot for its last run. Every other task that also occurs most times adds one more slot at the end. That is (most − 1) × (n + 1) + tied units, where tied counts the tasks occurring most times.
The other tasks fill the idle slots inside the frames. If there are more of them than idle slots, the frames simply stretch and no idle time is needed at all — the answer is then just the number of tasks. So the answer is the larger of the two. With A A A B B B and n = 2: (3 − 1) × 3 + 2 = 8, as in A B _ A B _ A B.
- Time
- O(n) — one count of the tasks
- Space
- O(1) — 26 counters
Solution · every language run against every case
class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: count = Counter(tasks) most = max(count.values()) # how often the commonest task occurs tied = sum(1 for c in count.values() if c == most) # how many tasks occur that often # The commonest task needs (most - 1) gaps of n after its runs, each frame n + 1 long, # then one last run holding every task tied for commonest. If other tasks overflow # the frames, no idle is needed at all and the answer is simply the number of tasks. return max(len(tasks), (most - 1) * (n + 1) + tied)