LeetCode · #621

Task Scheduler Solution

Given a list of tasks and a cooldown period n, return the minimum number of intervals the CPU needs to finish all tasks (including idle intervals).

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #621

🏗️

Pattern

Heap — greedy max-heap + cooldown queue

You are given an array of CPU tasks represented as characters and a cooldown period n. The same task must wait at least n intervals before being executed again. The CPU can either execute a task or be idle. Return the minimum number of intervals needed.

Example

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

Example 2

 Input: tasks = ["A","A","A","B","B","B"], n = 0 Output: 6 // No cooldown needed → just do all 6 tasks back-to-back 

Constraints

 • 1 ≤ tasks.length ≤ 10⁴ • tasks[i] is uppercase English letter (A–Z) • 0 ≤ n ≤ 100 

Section Two · Approach 1

Brute Force — Simulate with Tracking

Simulate time step by step. At each interval, find the task with the highest remaining count that isn't on cooldown. If none available, idle. Track last-used time for each task.

Why it works

Greedy choice — always picking the most frequent available task minimizes future idle slots. The simulation faithfully models the problem.

Why we can do better

Problem: Scanning all 26 tasks at each time step to find the best available is wasteful. A max-heap gives the highest-frequency task in O(log 26) = O(1), and a cooldown queue tracks when tasks become available again.

Java — Greedy scan

 // At each tick: scan all 26 tasks, find one with highest count // where (time - lastUsed[task]) > n. If none, idle. // O(totalTime × 26) — works but not clean 

Python — Greedy scan

# Same approach — simulate each tick, scan available tasks

Metric	Value
Time	O(totalTime × 26)
Space	O(26) = O(1)

Section Three · Approach 2

Max-Heap + Cooldown Queue — O(n)

Use a max-heap of remaining task counts (most frequent first) and a queue of tasks on cooldown. Each tick: pop the most frequent task from the heap, decrement its count, put it on cooldown with a "ready at" timestamp. When a queued task's cooldown expires, push it back to the heap.

💡 Mental model: Imagine a restaurant kitchen with one burner and several dishes to cook. The chef always picks the dish with the most servings left (max-heap). After cooking one serving, that dish goes to a "rest" shelf for n minutes (cooldown queue). When its rest time is up, it returns to the prep counter (heap). If no dish is ready, the chef waits (idle). Prioritizing the most-needed dish minimizes total idle time.

Algorithm

Step 1: Count frequencies. Push all non-zero counts into a max-heap.
Step 2: Initialize time = 0.
Step 3: While heap or queue is non-empty:
Increment time.
If heap non-empty: pop max count, decrement it. If count > 0, add to queue as (count, time + n).
If queue front's "ready at" == current time, push it back to heap.
Step 4: Return time.

🎯 When to recognize this pattern:

Any problem involving greedy scheduling with cooldowns — "process the most urgent item, wait before reprocessing." The signal is a repeated task with a mandatory gap.
This appears in LC 621 (Task Scheduler), LC 358 (Rearrange String k Distance Apart), and LC 767 (Reorganize String — cooldown of 1).

Math formula alternative:

The answer is max(len(tasks), (maxFreq - 1) × (n + 1) + countOfMaxFreq).
The first term handles cases where tasks fill all gaps; the second calculates the frame-based schedule.
Both approaches yield the same result.

Section Four · Trace

Visual Walkthrough

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

Max-Heap + Cooldown Queue — schedule 6 tasks with n=2

Section Five · Implementation

Code — Java & Python

Java — Max-Heap + Cooldown Queue

 import java.util.*;
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char t : tasks) freq[t - 'A']++;
PriorityQueue<Integer> heap =
new PriorityQueue<>(Collections.reverseOrder()); // max-heap for (int f : freq)
if (f > 0) heap.offer(f);
Queue<int[]> cooldown = new LinkedList<>(); // [count, readyAt] int time = 0;
while (!heap.isEmpty() || !cooldown.isEmpty()) {
            time++;
if (!heap.isEmpty()) {
int count = heap.poll() - 1; // execute one instance if (count > 0)
                    cooldown.offer(new int[]{count, time + n});
            }
if (!cooldown.isEmpty() && cooldown.peek()[1] == time)
                heap.offer(cooldown.poll()[0]); // cooldown expired
}
return time;
    }
}

Python — Max-Heap + Cooldown Queue

 from collections import Counter, deque
import heapq
class Solution:
def leastInterval(self, tasks: list[str], n: int) -> int:
        freq = Counter(tasks)
        heap = [-f for f in freq.values()] # max-heap (negate)
heapq.heapify(heap)

        cooldown = deque() # (neg_count, ready_at)
time = 0 while heap or cooldown:
            time += 1 if heap:
                count = heapq.heappop(heap) + 1 # +1 because negated if count < 0: # still has tasks left
cooldown.append((count, time + n))
if cooldown and cooldown[0][1] == time:
                heapq.heappush(heap, cooldown.popleft()[0])
return time

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Simulation (scan all tasks)	O(T × 26)	O(26)	T = total intervals including idle
Max-Heap + Queue ← optimal	O(T × log 26) ≈ O(T)	O(26) = O(1)	Heap of at most 26 tasks. Clean simulation.
Math formula	O(n)	O(1)	Direct calculation. Harder to derive but fastest.

Math formula explained:

max(len(tasks), (maxFreq - 1) × (n + 1) + maxCount) where maxCount = number of tasks with frequency equal to maxFreq.
The first term handles the "no idle needed" case; the second calculates the frame-based minimum.
Both O(n) and O(1) space.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
n = 0	`["A","A","B"], n=0`	No cooldown → answer = len(tasks) = 3. No idle ever.
Single task type	`["A","A","A"], n=2`	A _ _ A _ _ A → 7 intervals. All gaps are idle.
All distinct	`["A","B","C"], n=2`	A B C → 3 intervals. No repeats means no cooldown.
Large cooldown	`["A","A"], n=100`	A + 100 idles + A = 102 intervals.
Many tasks fill gaps	`["A","A","B","B","C","C"], n=1`	A B C A B C → 6 intervals. Enough variety to avoid idle.
Multiple max-frequency tasks	`["A","A","B","B"], n=2`	A B _ A B → 5. Both A and B are max-freq → last frame has 2 tasks.

⚠ Common Mistake: In the heap approach, forgetting to handle the idle case. When the heap is empty but the cooldown queue is non-empty, the CPU must idle — time still increments. If you only increment time when processing a task, you'll under-count idle intervals.

← Back to Heap problems

LearningTree

LC 621 · Task Scheduler — Solution & Explanation | DSA Guide