Task Scheduler (LeetCode 621)

The problem

You get a list of tasks, each a capital letter, and a cooldown n. The CPU runs one task per time slot, or sits idle. Two runs of the same task must be at least n slots apart. Return the minimum number of slots needed to finish every task. Tasks can run in any order.

Input:  tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

One best schedule is A B idle A B idle A B. Each A is 3 slots after the previous A, and two idle slots can’t be avoided.

How to think about it

Start with the simulation. At each slot, run the available task with the most remaining copies (a max-heap of counts), and park used tasks in a cooldown queue until they’re ready again. That’s the heap approach, and it works in O(total slots · log 26). But it simulates every idle slot one by one, and the answer can be worked out directly.

The key insight: the most frequent task decides the shape. Say A appears maxf times. Its copies must be spread out, so the schedule looks like maxf - 1 blocks of length n + 1 (an A followed by n slots of cooldown), then one final A. That’s (maxf - 1) * (n + 1) + 1 slots, and you can’t go lower.

Ties add to the tail. If several tasks share the top count maxf (here A and B), each one needs a place in the last block as well. So the frame is (maxf - 1) * (n + 1) + maxcount, where maxcount is how many tasks tie for the top. Every other task has fewer copies, so it fits into the idle gaps of the frame without breaking any cooldown.

When there are no idle slots left. With many different tasks, the gaps fill up and the frame overflows. Then nothing ever has to wait, and the answer is just len(tasks). So the answer is the larger of the two. Which pattern is this? It sits in the heaps lesson because the simulation uses a max-heap of counts, and it reappears under greedy. The tell is “most frequent first, with a cooldown”.

Approach

1. Count each task.
2. Let maxf be the highest count and maxcount the number of tasks with that count.
3. Compute the frame size (maxf - 1) * (n + 1) + maxcount.
4. Return the larger of that and len(tasks).

Solution

from collections import Counter
def least_interval(tasks, n):
    cnt = Counter(tasks); maxf = max(cnt.values())
    maxcount = sum(1 for v in cnt.values() if v == maxf)            # tasks tied for the top count
    return max(len(tasks), (maxf - 1) * (n + 1) + maxcount)          # frame, unless tasks overflow it
# least_interval(["A","A","A","B","B","B"], 2) -> 8

The same solution appears in the greedy practice set; the logic is identical.

Dry run

Three inputs, showing both sides of the max:

In the first row, the frame needs idle time. In the last two, the tasks overflow the frame, so no slot is ever idle.

Complexity

• Time: O(n) in the number of tasks. Counting is one pass; the rest looks at at most 26 counts.
• Space: O(1). The counter holds at most 26 letters.

Edge cases and pitfalls

• n = 0: no cooldown, so the answer is always len(tasks). The max handles it.
• One task type, ["A","A","A","A"] with n = 3: the frame is 3 · 4 + 1 = 13, almost all idle.
• Forgetting the ties. Using + 1 instead of + maxcount gives 7 on the example instead of 8.
• Forgetting len(tasks). Without the max, many distinct tasks give an answer that is too small.
• The heap simulation is a fine answer if you can’t recall the formula. It’s also what you need if the question asks for the schedule itself, not just its length.

Related problems

• Reorganize String (LeetCode 767): the same idea with cooldown 1, where you must build the actual string.
• Last Stone Weight (LeetCode 1046): a straightforward max-heap simulation.
• Top K Frequent Elements (LeetCode 347): another problem that starts with counting frequencies.