A CPU must run a list of tasks, each labelled with a capital letter and taking one unit of time. In each unit the CPU either runs one task or stays idle. Two runs of the same task must be separated by at least n units. Tasks can run in any order. Return the minimum number of units needed to finish all tasks.
- 1 <= tasks.length <= 10^4
- tasks[i] is an uppercase English letter
- 0 <= n <= 100
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Simulating with a max-heap and a cooldown queue works in O(total time). A counting argument is faster. Let the most frequent task appear maxf times. Its runs form maxf - 1 full blocks of length n + 1, plus a last block holding every task that also has frequency maxf (countMax of them). Other tasks fill the idle slots inside the blocks. If there are more tasks than slots, there is no idle time at all and the answer is just the number of tasks. So the answer is the larger of the two.
Algorithm
- Count how often each letter appears.
- Let
maxfbe the highest count andcountMaxthe number of letters with that count. - Compute
frame = (maxf - 1) * (n + 1) + countMax. - Return
max(frame, len(tasks)).
O(m), where m is the number of tasksSpace: O(1), only 26 counterslen(tasks) is a lower bound: when other tasks overflow the idle slots, you can widen the blocks and never need an idle unit. Some interviewers also ask for the actual schedule, which needs the heap simulation.class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: count = Counter(tasks) maxf = max(count.values()) count_max = sum(1 for c in count.values() if c == maxf) # tasks sharing the top frequency frame = (maxf - 1) * (n + 1) + count_max return max(frame, len(tasks))