Task Scheduler

Greedy heap simulation

Count each task type, then keep the available counts in a max-heap. At every time unit, run the available type with the most work left. A cooldown queue records when that type may return to the heap.

from collections import Counter, deque
import heapq
 
 
def least_interval(tasks: list[str], n: int) -> int:
    available = [-count for count in Counter(tasks).values()]
    heapq.heapify(available)
    cooling: deque[tuple[int, int]] = deque()
    time = 0
 
    while available or cooling:
        while cooling and cooling[0][0] <= time:
            _, count = cooling.popleft()
            heapq.heappush(available, count)
 
        if available:
            count = heapq.heappop(available) + 1
            if count < 0:
                cooling.append((time + n + 1, count))
        time += 1
 
    return time

Choosing the most frequent available type leaves the widest chance to fit its future copies around other work. The simulation is useful when you also need the actual schedule, but long idle stretches make it do work for time units that run no task.

Let T be the returned number of time units and m = len(tasks). Time O(T log 26), space O(1) because there are only 26 task types.

Maximum-frequency formula

Only the busiest task types can force idle time. Let:

• max_frequency be the largest count of any task type, and
• number_at_max be how many task types have that count.

The first max_frequency - 1 copies of a busiest type each begin a block of width n + 1: one task plus n separating slots. The last block needs one position for each type tied at the maximum. That gives:

(max_frequency - 1) * (n + 1) + number_at_max

Other tasks may fill every gap and make idle time disappear, so the answer can never be smaller than len(tasks). Take the larger quantity.

from collections import Counter
 
 
def least_interval(tasks: list[str], n: int) -> int:
    frequencies = list(Counter(tasks).values())
    max_frequency = max(frequencies)
    number_at_max = sum(
        count == max_frequency for count in frequencies
    )
    forced_length = (max_frequency - 1) * (n + 1) + number_at_max
    return max(len(tasks), forced_length)

When enough different work exists, len(tasks) wins and every slot runs a task. When one type dominates, the block calculation wins and the difference is forced idle time.

Time O(m), space O(1) for counting m tasks across a fixed 26-letter alphabet.