Problem 35 · Heaps

Task Scheduler

MediumClassic DSA & systems

01Problem

Given CPU tasks labeled by letters and a cooldown n between identical tasks, return the minimum number of time units to finish all tasks (idling allowed).

02Key insight

The most frequent task dictates the frame: (max_count - 1) * (n + 1) + number_of_tasks_tied_for_max, but never less than the total task count. A max-heap simulation gives the actual schedule.

03Solution

solution.pypython9 lines

from collections import Counter

def least_interval(tasks: list[str], n: int) -> int:
    counts = Counter(tasks)
    if not counts:
        return 0
    max_count = max(counts.values())
    tied = sum(1 for c in counts.values() if c == max_count)
    return max(len(tasks), (max_count - 1) * (n + 1) + tied)

Try it first.

TimeO(n)

SpaceO(1) (bounded alphabet)

tests.py · 4 passing

tests.pypython4 lines

assert least_interval(["A", "A", "A", "B", "B", "B"], 2) == 8
assert least_interval(["A", "C", "A", "B", "D", "B"], 1) == 6
assert least_interval(["A", "A", "A", "B", "B", "B"], 0) == 6
assert least_interval([], 3) == 0

04Staff-level follow-up

Tasks arrive online with priorities and per-type cooldowns? Simulate with a max-heap of ready tasks plus a min-heap (or queue) keyed by cooldown-expiry time, the same shape as a rate-limited job scheduler.