Task Scheduler

Task Scheduler looks like a simulation problem — "arrange the tasks on a timeline" — but the trick is that you never build the timeline. A little counting and one formula give the answer instantly.

The slow way first

The obvious idea: actually schedule it. Repeatedly pick the task with the most remaining copies that is off cooldown, place it, advance the clock, and insert idles when nothing is ready. With a heap this works, but it is fiddly and runs in O(total intervals) with a lot of bookkeeping.

The question to ask: what actually decides the length? Only the most frequent task does. It is the one forced to wait through cooldowns; everything else fits into the gaps it leaves behind.

The idea: the most frequent task builds a skeleton

Suppose the most frequent task appears maxFreq times. Picture it laid out in frames of width n + 1 — the task itself plus enough room for the cooldown. There are maxFreq - 1 full frames (the gaps between consecutive copies), and then a final placement of every task tied for the maximum.

The total is (maxFreq - 1) * (n + 1) + countOfMax. But if there are so many distinct tasks that every gap fills up with real work, no idle is ever needed and the answer is simply len(tasks). So we take the larger of the two.

Walk through it

Step through the animation. We count A and B (each 3 times), so maxFreq = 3 and countOfMax = 2. Two full frames of width n + 1 = 3 appear, each ending in an idle slot because there is no third task to fill it. Then a final row places one A and one B with no trailing idle. Count the slots: 2 × 3 + 2 = 8.

Pseudocode

count how often each task appears
maxFreq      = the largest of those counts
countOfMax   = how many tasks tie for that largest count
slots = (maxFreq - 1) * (n + 1)   # full frames forced by cooldown
slots = slots + countOfMax        # final placement, no trailing idle
return max(len(tasks), slots)     # never less than just running them all

The Python solution

def least_interval(tasks, n):
    from collections import Counter
    counts = Counter(tasks)
    max_freq = max(counts.values())
    count_of_max = sum(1 for c in counts.values()
                       if c == max_freq)
    slots = (max_freq - 1) * (n + 1)
    slots += count_of_max
    return max(len(tasks), slots)

• Counter(tasks) gives the frequency of every task in one pass.
• max_freq is how often the busiest task runs — it sets the skeleton.
• count_of_max counts the tasks tied for that maximum; they share the final, idle-free row.
• (max_freq - 1) * (n + 1) is the maxFreq - 1 full frames, each n + 1 wide.
• We add count_of_max for the last placement, then take max with len(tasks) so a task-dense input that needs no idle is handled correctly.

Complexity

We count the tasks once and then do constant arithmetic. Because there are at most 26 distinct task letters, the space is effectively O(1) — a fixed-size frequency table.

When this pattern shows up

Practice