Task Scheduler — Greedy Formula and Max-Heap Simulation [LC 621]

Problem Statement#

Given a list of CPU tasks and a non-negative integer n representing the cooldown period, find the minimum number of intervals to finish all tasks. Each interval is one unit of time; the CPU can execute one task per interval or be idle. Same tasks must be at least n intervals apart.

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

Input:  tasks = ["A","A","A","B","B","B"], n = 0
Output: 6

Why This Problem Matters#

LeetCode 621 is a favorite at Google, Meta, and Amazon because it requires two distinct skills: seeing a mathematical greedy formula, and implementing a heap-based simulation as a backup. Many candidates can memorize one approach but struggle to explain both or justify correctness.

The problem also demonstrates an important interview principle: sometimes a formula gives you the answer faster than any simulation, but the simulation provides the intuition that makes the formula obvious in retrospect. Knowing both shows algorithmic versatility.

The Core Insight#

Formula approach: The bottleneck is always the most frequent task. If the most frequent task appears max_count times, we need at least (max_count - 1) gaps of size (n + 1) between each pair of consecutive executions, plus the final slots for tasks with the same maximum frequency.

min_time = max((max_count - 1) * (n + 1) + count_of_max_tasks, len(tasks))

If n = 0 or there are enough distinct tasks to fill the gaps without idle time, the answer is simply len(tasks).

Heap simulation approach: Use a max-heap of (count, task). Each round, pull up to n+1 tasks (one complete "frame"), add them to a queue with their next-available time, and re-add them to the heap when the cooldown expires. Count total intervals including idle slots.

Visual Dry Run#

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

Frequencies: A=3, B=3. max_count = 3, count_of_max = 2.

Formula: (3-1) * (2+1) + 2 = 6 + 2 = 8

Frame layout:

[A, B, idle, A, B, idle, A, B]
  1  2    3  4  5     6  7  8  = 8 intervals

Check: max(8, 6) = 8. Answer = 8.

With n=0: no cooldown needed, answer = 6 = len(tasks).

Solution (Optimal)#

from collections import Counter
import heapq
from collections import deque
 
class Solution:
    def leastInterval(self, tasks, n):
        # Formula approach - O(1) after counting
        count = Counter(tasks)
        max_count = max(count.values())
        num_max = sum(1 for v in count.values() if v == max_count)
        return max(len(tasks), (max_count - 1) * (n + 1) + num_max)

var leastInterval = function(tasks, n) {
    const count = {};
    for (const t of tasks) count[t] = (count[t] || 0) + 1;
    const maxCount = Math.max(...Object.values(count));
    const numMax = Object.values(count).filter(v => v === maxCount).length;
    return Math.max(tasks.length, (maxCount - 1) * (n + 1) + numMax);
};

Time: O(tasks) — one pass to count frequencies, O(1) formula Space: O(1) — at most 26 distinct task types

Common Mistakes#

• Forgetting the max(len(tasks), formula) — when there are many distinct tasks, no idle time is needed and the answer is just len(tasks)
• Off-by-one in the formula — (max_count - 1) frames of size (n + 1) plus the final group
• Not counting all tasks with maximum frequency — multiple tasks tied for the max each get a slot in the last frame
• Implementing heap simulation incorrectly — must track when each task becomes available again, not just its remaining count
• Assuming the most frequent single task always determines the answer — ties in frequency add slots to the last frame

Interview Tips#

• Start with the formula: explain the "frame" structure visually before writing code
• Draw: [A, B, idle | A, B, idle | A, B] for tasks=["A","A","A","B","B","B"], n=2
• Explain the max(len, formula) guard: if distinct tasks fill frames naturally, no idle time occurs
• If asked for the simulation, mention max-heap + cooldown queue — same result, more general
• The formula is O(1) after counting — emphasize the simplicity for strong candidates

Follow-up Questions#

• How would you implement the heap simulation instead of the formula? (Max-heap of counts, cooldown deque, re-add when available)
• What if tasks have weights (some take multiple time units)? (Heap simulation generalizes; formula breaks down)
• What if there's no cooldown (n=0)? (Answer is simply len(tasks) — the max guard handles this)
• What if you want the actual schedule, not just the minimum time? (Simulation approach is needed — track which task fills each slot)
• Can the answer ever be less than len(tasks)? (No — you must execute all tasks, so len(tasks) is the lower bound)

Key Takeaways#

• LeetCode 621 is asked at Google, Meta, and Amazon — requires both formula insight and simulation fluency
• Most frequent task creates max_count - 1 mandatory frames of size n + 1 between its executions
• Formula: max(len(tasks), (max_count - 1) * (n + 1) + count_of_tasks_with_max_freq)
• The max(len(tasks), formula) guard handles the case where distinct tasks fill all gaps without idle slots
• Time O(n) for counting, O(1) for formula — effectively O(tasks) total; Space O(1) — at most 26 task types
• Heap simulation is equally valid: max-heap of task counts, cooldown queue, re-add when cooldown expires
• Explaining the frame structure visually is the clearest way to justify the formula to an interviewer