Task Scheduler — Greedy Cooldown Formula and Priority Queue

Problem Statement#

Given a characters array tasks, with each character representing a different task. CPU can complete one task per unit time. For each unit time, the CPU could complete either one task or be idle. Tasks can be done in any order. There is a cooldown interval n between two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Constraints:

• 1 <= tasks.length <= 10^4
• tasks[i] is an uppercase English letter.
• The integer n is in the range [0, 100].

Input:  tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A→B→idle→A→B→idle→A→B. 8 intervals.

Input:  tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: A dominates. 6 A's with cooldown 2 = 5 gaps of 3 + last A = 16.

Input:  tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: No cooldown, just execute all tasks. n=0 means no restriction.

Why This Problem Matters#

LC 621 is a FAANG classic at Amazon, Google, and Facebook. It teaches a critical greedy insight: when you have constrained scheduling with cooldowns, the most frequent task is the bottleneck.

The problem appears in:

• OS process scheduling: CPU scheduling with process cooldowns.
• Rate limiting: ensuring a service call is not made more often than once every n seconds.
• Network packet scheduling: spacing out packets from the same source.

The problem has two valid approaches: a mathematical formula (O(n) time) and a priority queue simulation (O(n log k) time). The formula is interview-optimal; the simulation is more generalizable to harder scheduling variants.

The Core Insight#

Greedy insight: Schedule the most frequent task first in every slot. The most frequent task determines the "frame" structure — a frame has n+1 slots (one for the most frequent task plus n slots for other tasks or idles).

Formula derivation:

Let f = frequency of the most frequent task. Let count_max = number of tasks with frequency f.

The optimal schedule has f - 1 full frames of size n + 1, followed by a final partial frame of size count_max:

Total = (f - 1) * (n + 1) + count_max

However, if there are enough tasks to fill all frames without idles, the answer is simply len(tasks).

Result: max(len(tasks), (f - 1) * (n + 1) + count_max)

Intuition: Think of arranging tasks in rows of n + 1:

A _ _ A _ _ A B B

If we have enough other tasks to fill the _ gaps, no idles are needed and the answer is just the total number of tasks.

Visual Dry Run#

tasks = ["A","A","A","B","B","B"], n = 2

Frequencies: A=3, B=3. f=3, count_max=2. Formula: max(6, (3-1)*(2+1)+2) = max(6, 6+2) = max(6,8) = 8.

Schedule:

Frame 1: A B idle
Frame 2: A B idle
Frame 3: A B
Total slots: 3+3+2 = 8 ✓

tasks = ["A","A","A","B","B","B","C","C","C"], n = 2

Frequencies: A=B=C=3. f=3, count_max=3. Formula: max(9, (3-1)*(2+1)+3) = max(9,9) = 9.

Schedule: A B C A B C A B C = 9 (no idles needed). ✓

tasks = ["A","A","A","A","A","A"], n = 2

Frequencies: A=6. f=6, count_max=1. Formula: max(6, (6-1)*(2+1)+1) = max(6,16) = 16.

Schedule: A idle idle A idle idle A idle idle A idle idle A idle idle A = 16. ✓

Solution (Optimal)#

# Python — greedy formula, O(n) time, O(1) space (only 26 letters)
from collections import Counter
 
def leastInterval(tasks: list[str], n: int) -> int:
    freq = Counter(tasks)
 
    f = max(freq.values())                          # max frequency
    count_max = sum(1 for v in freq.values() if v == f)  # how many tasks have freq f
 
    # Formula: arrange most-frequent tasks in frames of size (n+1)
    # If enough other tasks exist to fill frames, no idles needed
    return max(len(tasks), (f - 1) * (n + 1) + count_max)

// JavaScript — greedy formula, O(n) time, O(1) space
function leastInterval(tasks, n) {
    const freq = new Array(26).fill(0);
    for (const task of tasks) {
        freq[task.charCodeAt(0) - 65]++;
    }
 
    const f = Math.max(...freq);
    const countMax = freq.filter(v => v === f).length;
 
    return Math.max(tasks.length, (f - 1) * (n + 1) + countMax);
}

# Python — Priority Queue simulation (generalizable to harder variants)
import heapq
from collections import Counter, deque
 
def leastIntervalHeap(tasks: list[str], n: int) -> int:
    freq = Counter(tasks)
    # Max-heap (negate for Python's min-heap)
    heap = [-cnt for cnt in freq.values()]
    heapq.heapify(heap)
 
    time = 0
    cooldown_queue = deque()  # (available_at_time, count)
 
    while heap or cooldown_queue:
        time += 1
 
        if heap:
            cnt = heapq.heappop(heap) + 1  # run the most frequent task (-1 to count)
            if cnt < 0:  # still has remaining occurrences
                cooldown_queue.append((time + n, cnt))
 
        if cooldown_queue and cooldown_queue[0][0] == time:
            _, cnt = cooldown_queue.popleft()
            heapq.heappush(heap, cnt)
 
    return time

Complexity:

Common Mistakes#

1. Forgetting max(len(tasks), formula). When tasks can fill all frames without idles, the formula gives a number less than len(tasks). The answer is never less than the number of tasks.

2. Thinking the formula gives (f-1)*(n+1) + f. The last "frame" contains only the tasks with frequency f — not n+1 slots. The correct last frame size is count_max, not f or n+1.

3. Not counting tasks with the maximum frequency. If multiple tasks tie for the highest frequency (e.g., A=3, B=3), count_max = 2, not 1. Missing this under-counts the last frame.

4. n = 0 edge case. When n = 0, no cooldown is needed — any order works and the answer is len(tasks). The formula handles this: (f-1)*1 + count_max = f - 1 + count_max. With A=3, B=3, n=0: 2*1 + 2 = 4, but len(tasks) = 6. max(6, 4) = 6. ✓

5. Heap simulation: incorrect cooldown logic. The cooldown_queue should track when a task becomes available again (time + n), not when n time units have elapsed (time + n - 1).

Interview Tips#

• Draw the "frame" picture: "Think of frames of size n+1. The most frequent task anchors each frame. The formula counts (f-1) full frames plus a final partial frame of size count_max."
• Offer both approaches: "The formula is O(n) and elegant. The heap simulation is O(n log k) but more generalizable — if the problem adds constraints like task priorities or dependencies, the heap is the right foundation."
• Mention the max: "The formula gives the minimum time assuming idles are needed. If we have enough tasks to fill all gaps, the answer is just the total task count — hence max(len(tasks), formula)."

Follow-up Questions#

1. Which tasks fill which slots? Return the actual schedule as an array. Use the heap simulation with a result array.
2. What if tasks have different durations? The formula breaks down — use the heap simulation with adjusted time tracking.
3. CPU Burst Scheduling with dependencies. If task B must run after A, model as a DAG and use topological order with the heap.
4. Multiple CPUs. With k CPUs, the cooldown constraint applies per CPU — more complex scheduling problem.
5. Reorganize String (LC 767) — related problem: can you rearrange a string so no two adjacent characters are the same? Same greedy insight.

Key Takeaways#

• Greedy formula: max(len(tasks), (f - 1) * (n + 1) + count_max) where f is the max frequency and count_max is how many tasks have that frequency.
• The formula comes from arranging tasks in frames of size n + 1, anchored by the most frequent task. The final frame contains only the count_max most-frequent tasks.
• Always take max(len(tasks), formula) — when there are enough tasks to fill all frames without idle, no idles are needed.
• The heap simulation is a more general approach for harder scheduling variants but has O(n log k) complexity vs O(n) for the formula.
• Both approaches are valid; the formula demonstrates mathematical insight while the heap demonstrates algorithmic depth.
• Connected problems: Reorganize String (LC 767, same greedy) and CPU Scheduling Design questions in system design interviews.