Task Scheduler — Queue + Heap Approach

Given tasks with a cooldown period n (same task must have at least n intervals between executions), find the minimum number of intervals needed to execute all tasks.

Greedy Formula Approach

The task with the highest frequency determines the structure:

from collections import Counter

def least_interval_formula(tasks, n):
    """
    Greedy formula approach.
    Time: O(t), Space: O(1) — at most 26 task types
    """
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for v in freq.values() if v == max_freq)

    # (max_freq - 1) groups of (n + 1) slots, plus final group
    result = (max_freq - 1) * (n + 1) + max_count

    return max(result, len(tasks))

Why This Works

Tasks: A=6, B=1, C=1, D=1, E=1, F=1, n=2

A _ _ | A _ _ | A _ _ | A _ _ | A _ _ | A
A B C | A D E | A F _ | A _ _ | A _ _ | A

(max_freq-1) = 5 groups of (n+1) = 3 slots = 15
Plus max_count = 1 (only A has max freq)
Total = 16

But we have 11 tasks, and 16 > 11, so answer is 16.

Simulation with Heap + Queue

This approach builds the actual schedule:

import heapq
from collections import Counter, deque

def least_interval(tasks, n):
    """
    Simulate scheduling with max-heap and cooldown queue.
    Time: O(t × n), Space: O(t)
    """
    freq = Counter(tasks)
    max_heap = [-cnt for cnt in freq.values()]
    heapq.heapify(max_heap)

    cooldown = deque()  # (available_time, remaining_count)
    time = 0

    while max_heap or cooldown:
        time += 1

        if max_heap:
            cnt = heapq.heappop(max_heap) + 1  # +1 because negative
            if cnt != 0:
                cooldown.append((time + n, cnt))

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

    return time

Trace (Simulation)

Tasks: ['A','A','A','B','B','B'], n=2

time=1: heap=[-3A,-3B] → run A(-2), cooldown=[(3,-2A)]
time=2: heap=[-3B] → run B(-2), cooldown=[(3,-2A),(4,-2B)]
time=3: heap=[] → idle, cooldown releases A → heap=[-2A], cooldown=[(4,-2B)]
time=4: heap=[-2A] → run A(-1), cooldown releases B → heap=[-2B], cool=[(6,-1A)]
time=5: heap=[-2B] → run B(-1), cooldown=[(6,-1A),(7,-1B)]
time=6: releases A → run A(0), cooldown=[(7,-1B)]
time=7: releases B → run B(0)
time=8: done

Schedule: A B _ A B _ A B → 8 intervals

Edge Cases

• n = 0 — no cooldown, answer is len(tasks)
• All unique tasks — no cooldown needed if enough variety
• Single task type — answer is (freq - 1) * (n + 1) + 1
• Multiple tasks tied for max frequency — max_count handles this

When to Use Each Approach

Related Problems

• Reorganize String (LeetCode 767) — no adjacent same characters
• Rearrange String k Distance Apart (LeetCode 358)
• Task Scheduler II (LeetCode 2365)