Problem
You're given a list of tasks (letters) and a cooldown n: the same task can't
run again until at least n other slots have passed (idle or otherwise).
Return the minimum total time needed to run every task, in any order you
choose.
Signal
"Space out repeated items with a fixed cooldown, minimize total time" is driven entirely by whichever task is most frequent — that task forces the most idle slots, and everything else just fills in around it. This is greedy counting, not a heap simulation, even though a heap-based simulation also works.
Approach
Find the highest frequency max_freq among tasks, and how many distinct tasks
share that frequency (max_count). Picture the most frequent task laid out
with n-wide gaps between repeats: that creates (max_freq - 1) full gaps of
size n + 1, plus one final slot for each task that's tied at max_freq.
Other, less-frequent tasks slot into those gaps for free. The answer is
whichever is larger: that idle-slot-based total, or simply the number of
tasks (when there are enough distinct tasks to fill every gap with no idling
at all).
Skeleton
freqs = count(tasks)
max_freq = max(freqs.values())
max_count = number of tasks with freq == max_freq
return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)
Solution
from collections import Counter
def least_interval(tasks: list[str], n: int) -> int:
freqs = Counter(tasks)
max_freq = max(freqs.values())
max_count = sum(1 for f in freqs.values() if f == max_freq)
return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)
Complexity
O(len(tasks)) time — one pass to count frequencies, then a constant-size scan over at most 26 distinct letters. O(1) space (bounded alphabet).
Pitfalls
- Simulating the schedule slot-by-slot with a max-heap + cooldown queue also gets the right answer and generalizes better if the interviewer adds constraints — but it's O(len(tasks) · log(alphabet)) for what's otherwise a closed-form O(n) count. Know both, lead with the formula for this exact ask.
- Forgetting the
max(len(tasks), ...)outer max — when there are many distinct tasks, there's no idle time at all and the gap formula alone can undercount. - Miscounting
max_countas "the max frequency value" instead of "the number of tasks that have that frequency" — those are different numbers.