Task Scheduler

Problem

Given a list of tasks (characters) and a cooldown period n, find the minimum number of intervals needed to execute all tasks. The same task must wait at least n intervals before being executed again.

Approach

Use a max-heap (negated counts) to always schedule the most frequent task first. After executing a task, place it in a cooldown queue with the time it becomes available. When that time arrives, push it back onto the heap. Alternate least_interval_formula skips the simulation entirely and computes the answer from the idle-slot math.

When to Use

Scheduling with cooldown constraints — "minimum time to complete all tasks with cooldown", "CPU scheduling", "rate-limited job execution". Max-heap ensures the most frequent task is scheduled first.

Complexity

Time	O(t) where t = total intervals (bounded by len(tasks) * (n+1))
Space	O(1) — at most 26 distinct task types

Source

"""Task scheduler with cooldown.

Problem:
    Given a list of tasks (characters) and a cooldown period n, find the
    minimum number of intervals needed to execute all tasks. The same task
    must wait at least n intervals before being executed again.

Approach:
    Use a max-heap (negated counts) to always schedule the most frequent
    task first. After executing a task, place it in a cooldown queue with
    the time it becomes available. When that time arrives, push it back
    onto the heap. Alternate least_interval_formula skips the simulation
    entirely and computes the answer from the idle-slot math.

When to use:
    Scheduling with cooldown constraints — "minimum time to complete all
    tasks with cooldown", "CPU scheduling", "rate-limited job execution".
    Max-heap ensures the most frequent task is scheduled first.

Complexity:
    Time:  O(t) where t = total intervals (bounded by len(tasks) * (n+1))
    Space: O(1) — at most 26 distinct task types
"""

import heapq
from collections import Counter, deque
from typing import TYPE_CHECKING

if TYPE_CHECKING:
    from collections.abc import Sequence


def least_interval(tasks: Sequence[str], n: int) -> int:
    """Return the minimum number of intervals to complete all tasks.

    >>> least_interval(["A", "A", "A", "B", "B", "B"], 2)
    8
    """
    if not tasks:
        return 0

    counts = list(Counter(tasks).values())
    max_heap = [-c for c in counts]
    heapq.heapify(max_heap)

    time = 0
    cooldown: deque[tuple[int, int]] = deque()  # (available_time, neg_count)

    while max_heap or cooldown:
        time += 1

        if max_heap:
            cnt = heapq.heappop(max_heap) + 1  # execute one (cnt is negative)
            if cnt:  # task still has instances left; requeue after cooldown
                cooldown.append((time + n, cnt))

        if cooldown and cooldown[0][0] == time:
            heapq.heappush(max_heap, cooldown.popleft()[1])

    return time


# --- formula alternate: idle-slot math instead of simulating the heap ---
def least_interval_formula(tasks: Sequence[str], n: int) -> int:
    """Return the minimum intervals using the idle-slot formula, no simulation.

    >>> least_interval_formula(["A", "A", "A", "B", "B", "B"], 2)
    8
    """
    if not tasks:
        return 0

    counts = Counter(tasks).values()
    max_count = max(counts)
    # slots after the most frequent task's last-but-one run, plus ties for the max
    num_max = sum(1 for c in counts if c == max_count)
    return max(len(tasks), (max_count - 1) * (n + 1) + num_max)