Task Scheduler: Greedy Frequency Math With a Heap Proof

"Task Scheduler" is a Medium-level staple in Meta, Amazon, Microsoft loops, and it is a textbook fit for the Top-K and Heaps pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 7 of 11 in the Top-K and Heaps arc.

The Problem

Given tasks (letters) and a cooldown n between same-letter executions, each task taking one unit, return the minimum units to finish everything. A Meta staple with two accepted solutions: heap simulation, and a closed-form frame argument — the strongest candidates present both.

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

Recognizing the Top-K and Heaps Pattern

When a problem asks for the k largest, smallest, closest, or most frequent — or for repeated access to an extreme while data changes — a heap gives O(log n) insertion and O(1) access to the extreme. The signature trick: keep a bounded heap of size k with the opposite polarity (a min-heap to track the k largest), evicting the root on overflow. Python's heapq is a min-heap; negate values for max behavior.

Always schedule the most-frequent available task — a greedy on a mutating collection, which is heap territory (max-heap plus a cooldown queue). The structure of the optimal schedule — frames built around the most frequent task — also yields pure arithmetic, and the heap justifies why the formula holds.

The Approach

Formula: with f_max the top frequency and c tasks sharing it, the frame layout needs (f_max − 1) · (n + 1) + c slots; when tasks are plentiful they fill every idle slot and the answer floors at len(tasks). Take the max of the two.

Heap simulation: pop up to n + 1 distinct most-frequent tasks per round, decrement, re-queue after cooldown — O(total) with a 26-bounded heap. Present the formula, justify with the frame picture, keep the simulation in your pocket for the 'what if priorities change at runtime?' follow-up.

Python Solution

from collections import Counter


def least_interval(tasks: list[str], n: int) -> int:
    """Minimum time units with cooldown n between equal tasks."""
    counts = Counter(tasks)
    f_max = max(counts.values())
    c = sum(1 for v in counts.values() if v == f_max)
    frames = (f_max - 1) * (n + 1) + c
    return max(frames, len(tasks))

Complexity

• Time: O(t) — one counting pass over t tasks; the formula is O(26)
• Space: O(1) — a 26-letter counter

Interview Tips and Follow-Ups

• Draw the frame picture ((f_max − 1) rows of n + 1, plus the c-wide last row) — the formula without the picture sounds memorized, and interviewers test that.
• The max(..., len(tasks)) branch is where surplus task variety eliminates idles — explain why extra distinct tasks always fit into idle slots.
• If asked for the actual schedule (not just its length), the formula dies and the heap simulation is the answer — know both for exactly this reason.

That wraps part 7 of the Top-K and Heaps arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.