Amazon — Task Scheduler (Greedy + Frequency Heap)

Problem Statement#

Given a list of CPU tasks labeled A-Z and a cooldown period n, find the minimum number of intervals needed to finish all tasks. Between two same tasks there must be at least n intervals (idle or different tasks).

Constraints:

• 1 <= tasks.length <= 10^4
• tasks[i] is 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#

Task Scheduler (LeetCode 621) is one of Amazon's most frequently asked medium-hard problems, appearing in both phone screens and onsites. It directly models CPU process scheduling — a concept every Amazon systems engineer encounters when building services that rate-limit operations, throttle API calls, or batch background jobs.

The naive simulation places tasks one by one on a timeline, but the mathematical insight is more elegant: the answer is determined by the most frequent task. If task A appears f times and cooldown is n, the minimum intervals without idles is (f-1) * (n+1) + count_of_tasks_with_max_freq. The total is the maximum of this formula and the actual task count.

The greedy simulation with a max-heap is what most interviewers expect to see coded — it handles edge cases naturally and extends to more complex scheduling variants. Microsoft and Google also ask scheduling problems, making this a broadly applicable pattern.

The Core Insight#

Two approaches work:

1. Math formula: result = max(len(tasks), (max_freq - 1) * (n + 1) + count_of_max_freq_tasks)
2. Greedy simulation: Use a max-heap of (frequency, task). At each time step, pop up to n+1 tasks (or idle), decrement frequencies, and push back non-zero ones.

The mathematical approach is O(N) and elegant for interviews. The heap simulation is O(N log 26) = O(N) and more generalizable.

Visual Dry Run#

tasks = [A,A,A,B,B,B], n=2. Frequencies: A=3, B=3.

Formula: max_freq=3, count=2, result = max(6, (3-1)*(2+1)+2) = max(6, 8) = 8.

Solution (Optimal)#

from collections import Counter
import heapq
 
class Solution:
    def leastInterval(self, tasks: list, n: int) -> int:
        freq = Counter(tasks)
        max_heap = [-f for f in freq.values()]
        heapq.heapify(max_heap)
 
        time = 0
        while max_heap:
            cycle = []
            for _ in range(n + 1):
                if max_heap:
                    cycle.append(heapq.heappop(max_heap))
            for f in cycle:
                f += 1  # increment because stored as negative
                if f < 0:
                    heapq.heappush(max_heap, f)
            time += n + 1 if max_heap else len(cycle)
        return time
 
    def leastIntervalMath(self, tasks: list, n: int) -> int:
        freq = Counter(tasks)
        max_freq = max(freq.values())
        count_max = sum(1 for f in freq.values() if f == max_freq)
        return max(len(tasks), (max_freq - 1) * (n + 1) + count_max)

var leastInterval = function(tasks, n) {
    const freq = new Array(26).fill(0);
    for (const t of tasks) freq[t.charCodeAt(0) - 65]++;
    const maxFreq = Math.max(...freq);
    const countMax = freq.filter(f => f === maxFreq).length;
    return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countMax);
};

Time: O(N) — counting frequencies is O(N), formula is O(26) = O(1) Space: O(1) — only frequency array of size 26

Common Mistakes#

• Returning only the formula without checking max(len(tasks), formula) — fails when tasks fill all slots naturally
• Confusing cooldown n with cycle length n+1 — off-by-one in the formula
• Using min-heap instead of max-heap in the simulation approach
• Not handling n=0 (no cooldown) — formula still works: max(len(tasks), max_freq + count_max - 1)
• Counting distinct tasks with max frequency incorrectly

Interview Tips#

• Present the math formula first — it impresses interviewers and is O(N)
• Then offer to implement the heap simulation if asked for a more generalized approach
• The key insight to articulate: idle slots are only added when the most frequent task creates gaps
• Mention this models real CPU round-robin scheduling with a cooldown between repeated processes
• Edge case to check: all tasks the same type vs all different types

Follow-up Questions#

• What if tasks have different durations? — Weighted scheduling; use priority queue by (finish_time, task)
• What if the cooldown applies across different tasks too? — General dependency graph scheduling
• How do you minimize total execution time vs number of intervals? — Remove idles; just count tasks when n=0
• What is the minimum number of idle slots? — max(0, (max_freq-1)*n - sum_of_remaining_tasks)
• How would you reconstruct the actual schedule? — Store task IDs in the heap, emit them in order

Key Takeaways#

• The answer is max(total tasks, (max_freq - 1) * (n+1) + count_of_tasks_with_max_frequency)
• Idle slots are inserted only to fill cooldown gaps created by the most frequent task
• The cycle length is n+1, not n — the task itself occupies one slot in the cycle
• When n=0, the formula reduces to the total task count — no idle slots ever needed
• Amazon tests this to evaluate greedy thinking, scheduling knowledge, and formula derivation under pressure
• The heap simulation handles arbitrary task sets and generalizes to weighted/dependent task scheduling
• Both approaches run in O(N) time with O(1) or O(26) space — far better than any simulation approach