Task Scheduler

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    A CPU must run a list of tasks, each labelled with a letter A–Z; every task takes one time unit. Tasks may run in any order, but two runs of the same letter must have at least n time units between them, during which the CPU runs other tasks or sits idle. Return the minimum number of time units needed to finish all tasks.

    Original problem: LeetCode 621. It shows up both as a heap simulation question and as a counting question with a neat closed formula; strong candidates know both and can explain why the formula is right.

    Example

    With n = 2, the three A's must be at least 3 slots apart. B and C fill most gaps, and one idle slot is unavoidable: 7 time units in total.
    With n = 2, the three A's must be at least 3 slots apart. B and C fill most gaps, and one idle slot is unavoidable: 7 time units in total.
    Input:  tasks = [A, A, A, B, B, C], n = 2
    Output: 7          # A B C A B idle A
    Input:  tasks = [A, A, A, B, B, B, C, C, D, D], n = 2   ->  10    # no idle needed
    Input:  tasks = [A, A, A, A], n = 3                     ->  13

    Constraints (assumed)

    • 1 ≤ number of tasks ≤ 10⁴; letters A–Z; 0 ≤ n ≤ 100.

    What this question tests

    • Seeing that only the most frequent tasks force idle time.
    • Turning that into a formula, including the case where no idle time is needed.
    • Alternatively, a correct greedy simulation with a max-heap and a cooldown queue.

    Questions to ask first

    1. Can tasks run in any order? (Here: yes.)
    2. Does n mean n slots in between, or n time units after? (Here: at least n other slots between two runs of the same task.)
    3. Do I return the length or the schedule? (Here: the length.)
    4. Can n be 0? (Yes; then the answer is the number of tasks.)