Task Scheduler — LeetCode 621 Greedy Heap Pattern

Problem Statement#

Given a list of CPU tasks (uppercase letters) and a non-negative cooldown n, find the minimum total CPU intervals needed to finish all tasks. Same task must be at least n intervals apart; otherwise CPU is idle.

Constraints:

• 1 <= tasks.length <= 10^4
• tasks[i] is an uppercase English letter
• 0 <= n <= 100

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

Input:  tasks = ["A", "C", "A", "B", "D", "B"], n = 1
Output: 6

Why This Problem Matters#

LeetCode 621 Task Scheduler is a top-tier Amazon, Meta, and Google scheduling interview. It tests whether you can model a constrained greedy choice (always run the most-frequent ready task) with a max-heap plus cooldown queue. The closed-form formula is a beautiful follow-up that separates great candidates.

The problem has real-world resonance: rate limiting, quota smoothing, deduplication, and CPU scheduling all share this structure.

Keywords: "task scheduler interview", "FAANG cooldown problem", "greedy heap queue", "CPU scheduling math formula".

The Core Insight#

The bottleneck is the most frequent task. With max_count = max frequency and m tasks tied for max, the answer is at least:

(max_count - 1) * (n + 1) + m

That is the classic formula. If we have enough other tasks to fill the gaps, the actual time equals len(tasks). The answer is max(formula, len(tasks)).

The heap approach simulates: pop the most frequent ready task, decrement, send to cooldown. Always the highest-count task ready wins.

Visual Dry Run#

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

Total = 8.

Solution (Math Formula)#

from collections import Counter
 
class Solution:
    def leastInterval(self, tasks, n):
        cnt = Counter(tasks)
        max_count = max(cnt.values())
        ties = sum(1 for c in cnt.values() if c == max_count)
        return max(len(tasks), (max_count - 1) * (n + 1) + ties)

var leastInterval = function(tasks, n) {
    const cnt = new Map();
    for (const t of tasks) cnt.set(t, (cnt.get(t) || 0) + 1);
    let maxCount = 0, ties = 0;
    for (const c of cnt.values()) maxCount = Math.max(maxCount, c);
    for (const c of cnt.values()) if (c === maxCount) ties++;
    return Math.max(tasks.length, (maxCount - 1) * (n + 1) + ties);
};

Time: O(n) where n is tasks length. Space: O(1) — alphabet bounded.

Solution (Heap Simulation)#

import heapq
from collections import Counter, deque
 
class Solution:
    def leastIntervalHeap(self, tasks, n):
        h = [-c for c in Counter(tasks).values()]
        heapq.heapify(h)
        time = 0
        cool = deque()  # (ready_time, count)
        while h or cool:
            time += 1
            if h:
                c = heapq.heappop(h) + 1
                if c < 0:
                    cool.append((time + n, c))
            if cool and cool[0][0] == time:
                _, c = cool.popleft()
                heapq.heappush(h, c)
        return time

Time: O(N log K) where K = unique tasks. Space: O(K).

Common Mistakes#

• Forgetting the len(tasks) floor — formula can underestimate when many distinct tasks fill gaps.
• Counting ties as 1 instead of all tasks at max count.
• Using n instead of n + 1 in the formula (gap length includes the running slot).
• In simulation, decrementing toward 0 when stored as negative — increment instead.
• Not advancing time when only cooldown is non-empty — must idle.

Interview Tips#

• Open with the heap simulation; it is more obviously correct.
• Then derive the formula and explain the max(formula, len(tasks)) floor.
• Draw the rectangle with max_count - 1 rows of length n + 1 plus the last row of ties.
• Mention the formula's edge case when n = 0: answer = len(tasks).

Follow-up Questions#

• What if cooldown differs per task? Heap with per-task cooldown timestamps.
• What if you need the actual schedule (not just length)? Run the simulation and record output.
• Online tasks arriving in real time? Use heap + cooldown queue, no closed form.
• What if you can run K CPUs in parallel? Generalized formula and heap simulation.

Key Takeaways#

• LeetCode 621 has a beautiful closed-form: max(len(tasks), (max - 1) * (n + 1) + ties).
• The heap simulation works step-by-step: always run the most frequent ready task.
• The bottleneck is the most-frequent task; ties at max count squeeze in with no idle.
• Total time equals len(tasks) when distinct tasks are abundant.
• Cooldown queue is necessary in the heap simulation to delay re-entry.
• Generalizes to rate limiting, quota smoothing, and CPU scheduling.
• The formula is O(n) — beats simulation when the array is large.