Loading…

mediumHeapLC #621Frequently asked

Task Scheduler

Q: How do you solve Task Scheduler using the Greedy Max-Heap with Cooldown Queue approach?

When to use it: Lead with this — it builds intuition and can produce the actual schedule. Phrase the greedy as 'always run the most frequent task that's currently available'. Simulate the CPU greedily, one cooldown-sized round at a time. **The greedy choice.** At any tick, the task with the *most remaining copies* is the most urgent — delaying it risks forcing idles later because it needs the most gaps. So we always run the highest-count available task. A max-heap of remaining counts gives us that task in O(log 26). **Processing in rounds of (cooldown + 1).** After running a task, it can't run again for `n` ticks, so a block of `n + 1` consecutive ticks can contain at most one copy of any single task. We therefore pop up to `n + 1` tasks from the heap per round, run each once (decrement its count), and stash the still-nonzero ones in a temporary list. At the end of the round we push the survivors back. If we exhaust the heap before filling `n + 1` slots *and* tasks remain in cooldown, the remaining slots are **idle** — and we still count them. **Counting time correctly.** Each round normally costs `n + 1` ticks (including idles). The exception is the *final* round: if the heap empties exactly, we only add the number of tasks actually run, not a full padded block — otherwise we'd over-count trailing idle. **Why greedy is optimal.** Running the most frequent task as early and often as legal spreads its copies maximally, which is exactly what minimises forced idle. Any schedule that delays the most frequent task can be rearranged to run it earlier without increasing length — a standard exchange argument. Time complexity: O(n) (heap ops over ≤ 26 types). Space complexity: O(26) = O(1).

Q: How do you solve Task Scheduler using the Gap-Filling Math Formula (Optimal O(1) Extra) approach?

When to use it: The elegant closed form. Derive it from the most-frequent task building a frame of gaps, then correct with max(len(tasks), frame). Derive the length directly from the frequency distribution. **Build the skeleton from the most frequent task.** Let `M` be the highest task count. Place those `M` copies with mandatory gaps between them: `A _ _ A _ _ A` for `M = 3, n = 2`. This creates `(M − 1)` gaps, each of width `n` (so width `n + 1` counting the task that opens it). The skeleton occupies `(M − 1) × (n + 1)` ticks, plus the final block. **Account for ties at the maximum.** If several tasks share the maximum frequency `M`, each contributes one task to that final trailing block. So add `tasksAtMaxFreq` (the count of task types whose frequency equals `M`). The skeleton size becomes `frame = (M − 1) × (n + 1) + tasksAtMaxFreq`. **Fill the gaps — and the crucial correction.** Every other task drops into the gaps. If the gaps have enough room, leftover capacity becomes *idle*, and `frame` is the answer. But if there are *so many* distinct tasks that they overflow the gaps, there is **no idle at all** — you just run tasks back to back, and the answer is simply `len(tasks)`. We can't return less than the number of tasks, so the final answer is `max(len(tasks), frame)`. **Why the max() is the whole subtlety.** Candidates frequently produce just `frame` and fail tests like `[A,C,A,B,D,B], n = 1`, where `frame` underestimates because the diverse tasks already pack tightly. Taking the max with `len(tasks)` fixes it in one stroke. Time complexity: O(n) to count. Space complexity: O(1).

LCPractice

Heap & Priority Queue · 4 of 9 · 10 min

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task takes one unit of time. For each unit of time, the CPU could complete either one task or be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter): there must be at least n units of time between any two same tasks.

Return the least number of intervals the CPU will take to finish all the given tasks.

In plain English

We schedule single-unit tasks on a CPU. The only constraint is that two runs of the *same* task must be separated by at least n other ticks (idle counts). We want the shortest total timeline. Order among different tasks is free, so we can rearrange to minimise idle time.

Examples

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Note: A → B → idle → A → B → idle → A → B. Three A's need two gaps of size 2; B's fill one slot each, leaving one idle per gap.

Example 2

Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Note: Enough distinct tasks to avoid any idle: e.g. A B C A B D. Answer equals len(tasks) = 6.

Example 3

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Note: No cooldown, run everything back to back: A A A B B B = 6 intervals.

Constraints

1 ≤ tasks.length ≤ 10⁴
tasks[i] is an uppercase English letter (only 26 distinct types)
0 ≤ n ≤ 100

Clarifying questions4First question: Do I need to output the actual schedule or just its length?Explore questions

Q1.Do I need to output the actual schedule or just its length?
Just the number of intervals. If a schedule were required I'd use the heap simulation, which can emit the sequence; the formula only gives the length.
Q2.Does idle time count toward the total?
Yes. If the CPU has to wait because every remaining task is on cooldown, each idle tick adds to the answer.
Q3.How many distinct task types are there?
At most 26 (uppercase letters). That bound makes the heap operations effectively constant per step.
Q4.What if n is 0?
No cooldown, so we can run tasks back to back — the answer is simply len(tasks).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The total time is dominated by the most frequent task. Greedy answer: always run the available task with the highest remaining count, using a max-heap plus a cooldown queue — O(n log 26) ≈ O(n). The O(1) math shortcut: ans = max(n, (maxFreq − 1) × (cooldown + 1) + countOfTasksWithMaxFreq). Both give the minimum number of intervals.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you see that the bottleneck is the most frequent task, can argue the greedy (run the highest-count available task) is optimal, and can derive the O(1) gap formula.

Where candidates slip

Trying to brute-force orderings, or forgetting to count idle slots, or using max(maxFreq−1)*(n+1)... but ignoring that the real answer can be len(tasks) when there are many distinct tasks.

How to stand out

Present the heap simulation for intuition and the ability to emit a schedule, then derive the closed-form formula and explain the max(len(tasks), frame) correction with a concrete 'lots of distinct tasks' example.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Greedy Max-Heap with Cooldown Queue	`O(n) (heap ops over ≤ 26 types)`	`O(26) = O(1)`	Lead with this — it builds intuition and can produce the actual schedule. Phrase the greedy as 'always run the most frequent task that's currently available'.	Read
2	Gap-Filling Math Formula (Optimal O(1) Extra)Optimal	`O(n) to count`	`O(1)`	The elegant closed form. Derive it from the most-frequent task building a frame of gaps, then correct with max(len(tasks), frame).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMin intervals with cooldown nNeed the actual schedule?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Greedy Max-Heap with Cooldown Queue

TimeO(n) (heap ops over ≤ 26 types)SpaceO(26) = O(1)

Lead with this — it builds intuition and can produce the actual schedule. Phrase the greedy as 'always run the most frequent task that's currently available'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

To minimise idle time, which task should you run first at each step — and why does running the most frequent one help?

2Hint 2Explore hint

Use a max-heap of remaining counts. Each 'round' lasts cooldown+1 ticks; greedily run up to cooldown+1 distinct tasks, decrementing each.

3Hint 3Explore hint

Tasks you run aren't available again until their cooldown passes — park them in a queue with a ready-time, and push them back into the heap when ready. Count every tick, including idles.

A · Core idea

Simulate the CPU greedily, one cooldown-sized round at a time.

The greedy choice. At any tick, the task with the most remaining copies is the most urgent — delaying it risks forcing idles later because it needs the most gaps. So we always run the highest-count available task. A max-heap of remaining counts gives us that task in O(log 26).

Processing in rounds of (cooldown + 1). After running a task, it can't run again for n ticks, so a block of n + 1 consecutive ticks can contain at most one copy of any single task. We therefore pop up to n + 1 tasks from the heap per round, run each once (decrement its count), and stash the still-nonzero ones in a temporary list. At the end of the round we push the survivors back. If we exhaust the heap before filling n + 1 slots and tasks remain in cooldown, the remaining slots are idle — and we still count them.

Counting time correctly. Each round normally costs n + 1 ticks (including idles). The exception is the final round: if the heap empties exactly, we only add the number of tasks actually run, not a full padded block — otherwise we'd over-count trailing idle.

Why greedy is optimal. Running the most frequent task as early and often as legal spreads its copies maximally, which is exactly what minimises forced idle. Any schedule that delays the most frequent task can be rearranged to run it earlier without increasing length — a standard exchange argument.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

The schedule timeline for A×3, B×3, n=2

round 1

Active call / nodeSupporting contextReturned stateNot active

Two gaps of size 2 around the A's; B's fill one slot each, one idle remains per gap.

Final result8

C · Code with teaching comments

Reference implementation previewpublic int leastInterval(char[] tasks, int n) { int[] freq = new int[26]; for (char c : tasks) freq[c - 'A']++; PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());Explore the full code

solution.javaJava

Greedy Max-Heap with Cooldown Queue — reference

4 teaching notes

1
public int leastInterval(char[] tasks, int n) {
2
    int[] freq = new int[26];
3
    for (char c : tasks) freq[c - 'A']++;
4
    PriorityQueue<Integer> heap =
5
        new PriorityQueue<>(Collections.reverseOrder());
6
    for (int f : freq) if (f > 0) heap.offer(f);
7
 
8
    int time = 0;
9
    while (!heap.isEmpty()) {
10
        // A block of n+1 ticks can hold at most one copy of any task — that's our round
11
        // length.
12
        int cycle = n + 1;
13
        List<Integer> leftover = new ArrayList<>();
14
        int run = 0;
15
        while (cycle > 0 && !heap.isEmpty()) {
16
            int cur = heap.poll();
17
            // Ran one copy; if copies remain, set it aside to re-add AFTER the round
18
            // (enforces cooldown).
19
            if (cur - 1 > 0) leftover.add(cur - 1);
20
            run++;
21
            cycle--;
22
        }
23
        for (int rem : leftover) heap.offer(rem);
24
        // Full block (n+1) if tasks remain; else only what we ran.
25
        // Full padded block while work remains; only the actually-run count on the
26
        // final round (no trailing idle).
27
        time += heap.isEmpty() ? run : n + 1;
28
    }
29
    return time;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n) (heap ops over ≤ 26 types) timeO(26) = O(1) spaceOpen the invariant and proofExplore the proof

The heap turns an abstract scheduling constraint into a concrete loop: 'each round, serve the busiest customers first, then send them to the back of the line for n turns.' Because there are only 26 task types, the heap is tiny and the whole thing runs in linear time over the task count.

ComplexityO(n) (heap ops over ≤ 26 types) time, O(26) = O(1) space — Every task instance is pushed/popped O(1) times; each heap op is O(log 26) = O(1). With n total task instances, the simulation is O(n). The heap and queue hold at most 26 entries → O(1) space.

E · Edge cases and pitfalls6tasks = [A,A,A], n = 2 — Only one type; A _ _ A _ _ A → 7 (heavy idle). Formula: (3−1)*3 + 1 = 7.Explore edge cases

Edge cases handled

tasks = [A,A,A], n = 2Only one type; A _ _ A _ _ A → 7 (heavy idle). Formula: (3−1)*3 + 1 = 7.
n = 0cycle = 1 each round; never idle; time = len(tasks).
many distinct tasksHeap rarely empties mid-round, so no idle; time = len(tasks).

Pitfalls

Adding a full n+1 block on the final round — over-counts trailing idle time.
Re-adding a task to the heap DURING the round instead of after — lets it run again before its cooldown.
Forgetting to negate in Python (or reversing the comparator in Java) — serves the least frequent task.

03.2

Approach 2 of 2 · Optimal

Gap-Filling Math Formula (Optimal O(1) Extra)

TimeO(n) to countSpaceO(1)

The elegant closed form. Derive it from the most-frequent task building a frame of gaps, then correct with max(len(tasks), frame).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine laying out only the most frequent task with the required gaps. How many fixed 'slots' does that skeleton have?

2Hint 2Explore hint

If the max frequency is M, there are (M−1) gaps, each needing (n+1) width, plus the final run of every task tied at frequency M.

3Hint 3Explore hint

Other tasks slot into those gaps. If they overflow the gaps (lots of distinct tasks), there's no idle at all — so the true answer is max(len(tasks), the skeleton size).

A · Core idea

Derive the length directly from the frequency distribution.

Build the skeleton from the most frequent task. Let M be the highest task count. Place those M copies with mandatory gaps between them: A _ _ A _ _ A for M = 3, n = 2. This creates (M − 1) gaps, each of width n (so width n + 1 counting the task that opens it). The skeleton occupies (M − 1) × (n + 1) ticks, plus the final block.

Account for ties at the maximum. If several tasks share the maximum frequency M, each contributes one task to that final trailing block. So add tasksAtMaxFreq (the count of task types whose frequency equals M). The skeleton size becomes frame = (M − 1) × (n + 1) + tasksAtMaxFreq.

Fill the gaps — and the crucial correction. Every other task drops into the gaps. If the gaps have enough room, leftover capacity becomes idle, and frame is the answer. But if there are so many distinct tasks that they overflow the gaps, there is no idle at all — you just run tasks back to back, and the answer is simply len(tasks). We can't return less than the number of tasks, so the final answer is max(len(tasks), frame).

Why the max() is the whole subtlety. Candidates frequently produce just frame and fail tests like [A,C,A,B,D,B], n = 1, where frame underestimates because the diverse tasks already pack tightly. Taking the max with len(tasks) fixes it in one stroke.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Scaffold built by the most frequent task

count

Active call / nodeSupporting contextReturned stateNot active

M=3 A's create 2 gaps of width n+1=3; B's fill one slot each, idle is leftover capacity.

Final result8

C · Code with teaching comments

solution.javaJava

Gap-Filling Math Formula (Optimal O(1) Extra) — optimal

4 teaching notes

1
public int leastInterval(char[] tasks, int n) {
2
    int[] freq = new int[26];
3
    for (char c : tasks) freq[c - 'A']++;
4
    int maxFreq = 0;
5
    // The most frequent task sets the scaffold height M.
6
    for (int f : freq) maxFreq = Math.max(maxFreq, f);
7
    int tasksAtMax = 0;
8
    // Count types tied at M — each adds one to the final trailing block.
9
    for (int f : freq) if (f == maxFreq) tasksAtMax++;
10
    // (M−1) gaps of width (n+1), plus the last block of the max-frequency tasks.
11
    int frame = (maxFreq - 1) * (n + 1) + tasksAtMax;
12
    // If many distinct tasks fill all gaps, no idle exists → answer can't be below
13
    // len(tasks).
14
    return Math.max(tasks.length, frame);
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) to count timeO(1) spaceOpen the invariant and proofExplore the proof

The most frequent task is a rigid scaffold; everything else is filler. Idle time is purely 'unfilled scaffold gaps', so the answer is the bigger of (scaffold size) and (you have to run every task anyway). One line of arithmetic captures a problem that looks like it needs full simulation.

ComplexityO(n) to count time, O(1) space — Counting frequencies and finding the maximum is O(n) over the task array (26-bounded). The formula itself is O(1). No auxiliary structure beyond a 26-entry count → O(1) space.

E · Edge cases and pitfalls6tasks = [A,C,A,B,D,B], n = 1 — M=2, tied tasks (A,B)=2 → frame = 1*2+2 = 4, but len=6 → answer 6. The max() is essential here.Explore edge cases

Edge cases handled

tasks = [A,C,A,B,D,B], n = 1M=2, tied tasks (A,B)=2 → frame = 1*2+2 = 4, but len=6 → answer 6. The max() is essential here.
n = 0frame = (M−1)*1 + ties ≤ len(tasks); max gives len(tasks).
single repeated task A×5, n=3frame = 4*4 + 1 = 17; len=5 → answer 17 (mostly idle).

Pitfalls

Returning `frame` without max(len(tasks), frame) — fails on inputs with many distinct tasks.
Forgetting to add tasksAtMaxFreq — undercounts the final trailing block on ties.
Using (M−1)*n instead of (M−1)*(n+1) — drops the task that opens each gap.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int leastInterval(char[] tasks, int n) { int[] freq = new int[26]; for (char c : tasks) freq[c - 'A']++; int maxFreq = 0; for (int f : freq) maxFreq = Math.max(maxFreq, f);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Formula without the max(len, frame) correction

When there are enough distinct tasks to fill all gaps, there is zero idle and the schedule is just len(tasks). The raw frame can be smaller than len(tasks), giving a wrong, too-small answer.

Explore the code comparison

Don't write this

frame = (max_freq - 1) * (n + 1) + tasks_at_max
return frame  # underestimates on diverse inputs

Write this instead

frame = (max_freq - 1) * (n + 1) + tasks_at_max
return max(len(tasks), frame)

Over-counting idle on the final heap round

If the heap empties mid-round, padding the time by a full n+1 block adds idle ticks that never happen at the end of the schedule.

Explore the code comparison

Don't write this

// always add a full block
time += n + 1;

Write this instead

// last round: add only the tasks actually run
time += heap.isEmpty() ? run : n + 1;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy max-heap with cooldown queue (or the gap-filling formula)

Code pattern to memorize

frame = (maxFreq - 1) * (cooldown + 1) + tasksAtMaxFreq
answer = max(len(tasks), frame)
# Heap version: each round pop up to (cooldown+1) most frequent,
# decrement, requeue after cooldown; count every tick incl. idles.

Rules to remember

1The schedule length is driven by the most frequent task — it sets a skeleton of (maxFreq−1) gaps of size cooldown.
2Greedy choice: among tasks off cooldown, always run the one with the highest remaining count to fill gaps fastest.
3Idle slots only appear when there aren't enough distinct tasks to fill the cooldown gaps — that's exactly what the formula's max(len(tasks), frame) captures.
4Answer is never less than len(tasks) (you must run every task at least once), so take the max with the gap formula.
5Only 26 task types (A–Z), so the heap cost has a constant factor → effectively O(n).

Use this pattern when

Scheduling identical jobs with a mandatory cooldown / cooling interval
'Minimum time/intervals to process all tasks with spacing constraints'
Rearranging items so identical ones are ≥ k apart (same family)
Greedy 'always process the most urgent/frequent next' problems

Choose another pattern when

No cooldown (n = 0) → answer is just len(tasks)
You must output the actual schedule, not just its length → use the heap, not the formula
Tasks have distinct durations/priorities beyond frequency → richer scheduling, not this template

Interview takeaway

Task Scheduler is a greedy problem where the most frequent task builds a rigid frame and everything else fills the gaps. A max-heap simulates it; a closed-form gap-counting formula nails it in O(1) extra. Recognise it whenever identical items must be spaced apart — it's the sibling of Rearrange String k Distance Apart.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternGreedy scheduling where the most frequent item sets the pace. Simulate with a max-heap + cooldown queue, or compute the gap-filling formula in O(1). Same family as Reorganize String and Rearrange String k Distance Apart.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Rearrange String k Distance Apart
Coming soon
Same max-heap + cooldown queue, but you must output a valid arrangement (or report impossible).
Reorganize String
Coming soon
Special case n = 1: no two identical chars adjacent; greedy on the most frequent char.
Task Scheduler II
Coming soon
Per-task cooldown via a hashmap of next-available times — a streaming variant.
Single-Threaded CPU
Coming soon
Heap by processing time with availability ordering — richer scheduling with a min-heap.

Same pattern

←

K Closest Points to Origin

Continue · Next problem

Merge k Sorted Lists

mediumHeapLC #621Frequently asked

Task Scheduler

LCPractice

Heap & Priority Queue · 4 of 9 · 10 min

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter): there must be at least n units of time between any two same tasks.

Return the least number of intervals the CPU will take to finish all the given tasks.

In plain English

Examples

Example 1

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Note: A → B → idle → A → B → idle → A → B. Three A's need two gaps of size 2; B's fill one slot each, leaving one idle per gap.

Example 2

Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Note: Enough distinct tasks to avoid any idle: e.g. A B C A B D. Answer equals len(tasks) = 6.

Example 3

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Note: No cooldown, run everything back to back: A A A B B B = 6 intervals.

Constraints

1 ≤ tasks.length ≤ 10⁴
tasks[i] is an uppercase English letter (only 26 distinct types)
0 ≤ n ≤ 100

Clarifying questions4First question: Do I need to output the actual schedule or just its length?Explore questions

Q1.Do I need to output the actual schedule or just its length?
Just the number of intervals. If a schedule were required I'd use the heap simulation, which can emit the sequence; the formula only gives the length.
Q2.Does idle time count toward the total?
Yes. If the CPU has to wait because every remaining task is on cooldown, each idle tick adds to the answer.
Q3.How many distinct task types are there?
At most 26 (uppercase letters). That bound makes the heap operations effectively constant per step.
Q4.What if n is 0?
No cooldown, so we can run tasks back to back — the answer is simply len(tasks).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you see that the bottleneck is the most frequent task, can argue the greedy (run the highest-count available task) is optimal, and can derive the O(1) gap formula.

Where candidates slip

Trying to brute-force orderings, or forgetting to count idle slots, or using max(maxFreq−1)*(n+1)... but ignoring that the real answer can be len(tasks) when there are many distinct tasks.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Greedy Max-Heap with Cooldown Queue	`O(n) (heap ops over ≤ 26 types)`	`O(26) = O(1)`	Lead with this — it builds intuition and can produce the actual schedule. Phrase the greedy as 'always run the most frequent task that's currently available'.	Read
2	Gap-Filling Math Formula (Optimal O(1) Extra)Optimal	`O(n) to count`	`O(1)`	The elegant closed form. Derive it from the most-frequent task building a frame of gaps, then correct with max(len(tasks), frame).	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Greedy Max-Heap with Cooldown Queue

TimeO(n) (heap ops over ≤ 26 types)SpaceO(26) = O(1)

Lead with this — it builds intuition and can produce the actual schedule. Phrase the greedy as 'always run the most frequent task that's currently available'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

To minimise idle time, which task should you run first at each step — and why does running the most frequent one help?

2Hint 2Explore hint

Use a max-heap of remaining counts. Each 'round' lasts cooldown+1 ticks; greedily run up to cooldown+1 distinct tasks, decrementing each.

3Hint 3Explore hint

Tasks you run aren't available again until their cooldown passes — park them in a queue with a ready-time, and push them back into the heap when ready. Count every tick, including idles.

A · Core idea

Simulate the CPU greedily, one cooldown-sized round at a time.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

The schedule timeline for A×3, B×3, n=2

round 1

Active call / nodeSupporting contextReturned stateNot active

Two gaps of size 2 around the A's; B's fill one slot each, one idle remains per gap.

Final result8

C · Code with teaching comments

solution.javaJava

Greedy Max-Heap with Cooldown Queue — reference

4 teaching notes

1
public int leastInterval(char[] tasks, int n) {
2
    int[] freq = new int[26];
3
    for (char c : tasks) freq[c - 'A']++;
4
    PriorityQueue<Integer> heap =
5
        new PriorityQueue<>(Collections.reverseOrder());
6
    for (int f : freq) if (f > 0) heap.offer(f);
7
 
8
    int time = 0;
9
    while (!heap.isEmpty()) {
10
        // A block of n+1 ticks can hold at most one copy of any task — that's our round
11
        // length.
12
        int cycle = n + 1;
13
        List<Integer> leftover = new ArrayList<>();
14
        int run = 0;
15
        while (cycle > 0 && !heap.isEmpty()) {
16
            int cur = heap.poll();
17
            // Ran one copy; if copies remain, set it aside to re-add AFTER the round
18
            // (enforces cooldown).
19
            if (cur - 1 > 0) leftover.add(cur - 1);
20
            run++;
21
            cycle--;
22
        }
23
        for (int rem : leftover) heap.offer(rem);
24
        // Full block (n+1) if tasks remain; else only what we ran.
25
        // Full padded block while work remains; only the actually-run count on the
26
        // final round (no trailing idle).
27
        time += heap.isEmpty() ? run : n + 1;
28
    }
29
    return time;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n) (heap ops over ≤ 26 types) timeO(26) = O(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6tasks = [A,A,A], n = 2 — Only one type; A _ _ A _ _ A → 7 (heavy idle). Formula: (3−1)*3 + 1 = 7.Explore edge cases

Edge cases handled

tasks = [A,A,A], n = 2Only one type; A _ _ A _ _ A → 7 (heavy idle). Formula: (3−1)*3 + 1 = 7.
n = 0cycle = 1 each round; never idle; time = len(tasks).
many distinct tasksHeap rarely empties mid-round, so no idle; time = len(tasks).

Pitfalls

Adding a full n+1 block on the final round — over-counts trailing idle time.
Re-adding a task to the heap DURING the round instead of after — lets it run again before its cooldown.
Forgetting to negate in Python (or reversing the comparator in Java) — serves the least frequent task.

03.2

Approach 2 of 2 · Optimal

Gap-Filling Math Formula (Optimal O(1) Extra)

TimeO(n) to countSpaceO(1)

The elegant closed form. Derive it from the most-frequent task building a frame of gaps, then correct with max(len(tasks), frame).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Imagine laying out only the most frequent task with the required gaps. How many fixed 'slots' does that skeleton have?

2Hint 2Explore hint

If the max frequency is M, there are (M−1) gaps, each needing (n+1) width, plus the final run of every task tied at frequency M.

3Hint 3Explore hint

Other tasks slot into those gaps. If they overflow the gaps (lots of distinct tasks), there's no idle at all — so the true answer is max(len(tasks), the skeleton size).

A · Core idea

Derive the length directly from the frequency distribution.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Scaffold built by the most frequent task

count

Active call / nodeSupporting contextReturned stateNot active

M=3 A's create 2 gaps of width n+1=3; B's fill one slot each, idle is leftover capacity.

Final result8

C · Code with teaching comments

solution.javaJava

Gap-Filling Math Formula (Optimal O(1) Extra) — optimal

4 teaching notes

1
public int leastInterval(char[] tasks, int n) {
2
    int[] freq = new int[26];
3
    for (char c : tasks) freq[c - 'A']++;
4
    int maxFreq = 0;
5
    // The most frequent task sets the scaffold height M.
6
    for (int f : freq) maxFreq = Math.max(maxFreq, f);
7
    int tasksAtMax = 0;
8
    // Count types tied at M — each adds one to the final trailing block.
9
    for (int f : freq) if (f == maxFreq) tasksAtMax++;
10
    // (M−1) gaps of width (n+1), plus the last block of the max-frequency tasks.
11
    int frame = (maxFreq - 1) * (n + 1) + tasksAtMax;
12
    // If many distinct tasks fill all gaps, no idle exists → answer can't be below
13
    // len(tasks).
14
    return Math.max(tasks.length, frame);
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) to count timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6tasks = [A,C,A,B,D,B], n = 1 — M=2, tied tasks (A,B)=2 → frame = 1*2+2 = 4, but len=6 → answer 6. The max() is essential here.Explore edge cases

Edge cases handled

tasks = [A,C,A,B,D,B], n = 1M=2, tied tasks (A,B)=2 → frame = 1*2+2 = 4, but len=6 → answer 6. The max() is essential here.
n = 0frame = (M−1)*1 + ties ≤ len(tasks); max gives len(tasks).
single repeated task A×5, n=3frame = 4*4 + 1 = 17; len=5 → answer 17 (mostly idle).

Pitfalls

Returning `frame` without max(len(tasks), frame) — fails on inputs with many distinct tasks.
Forgetting to add tasksAtMaxFreq — undercounts the final trailing block on ties.
Using (M−1)*n instead of (M−1)*(n+1) — drops the task that opens each gap.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Formula without the max(len, frame) correction

When there are enough distinct tasks to fill all gaps, there is zero idle and the schedule is just len(tasks). The raw frame can be smaller than len(tasks), giving a wrong, too-small answer.

Explore the code comparison

Don't write this

frame = (max_freq - 1) * (n + 1) + tasks_at_max
return frame  # underestimates on diverse inputs

Write this instead

frame = (max_freq - 1) * (n + 1) + tasks_at_max
return max(len(tasks), frame)

Over-counting idle on the final heap round

If the heap empties mid-round, padding the time by a full n+1 block adds idle ticks that never happen at the end of the schedule.

Explore the code comparison

Don't write this

// always add a full block
time += n + 1;

Write this instead

// last round: add only the tasks actually run
time += heap.isEmpty() ? run : n + 1;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy max-heap with cooldown queue (or the gap-filling formula)

Code pattern to memorize

frame = (maxFreq - 1) * (cooldown + 1) + tasksAtMaxFreq
answer = max(len(tasks), frame)
# Heap version: each round pop up to (cooldown+1) most frequent,
# decrement, requeue after cooldown; count every tick incl. idles.

Rules to remember

1The schedule length is driven by the most frequent task — it sets a skeleton of (maxFreq−1) gaps of size cooldown.
2Greedy choice: among tasks off cooldown, always run the one with the highest remaining count to fill gaps fastest.
3Idle slots only appear when there aren't enough distinct tasks to fill the cooldown gaps — that's exactly what the formula's max(len(tasks), frame) captures.
4Answer is never less than len(tasks) (you must run every task at least once), so take the max with the gap formula.
5Only 26 task types (A–Z), so the heap cost has a constant factor → effectively O(n).

Use this pattern when

Scheduling identical jobs with a mandatory cooldown / cooling interval
'Minimum time/intervals to process all tasks with spacing constraints'
Rearranging items so identical ones are ≥ k apart (same family)
Greedy 'always process the most urgent/frequent next' problems

Choose another pattern when

No cooldown (n = 0) → answer is just len(tasks)
You must output the actual schedule, not just its length → use the heap, not the formula
Tasks have distinct durations/priorities beyond frequency → richer scheduling, not this template

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Rearrange String k Distance Apart
Coming soon
Same max-heap + cooldown queue, but you must output a valid arrangement (or report impossible).
Reorganize String
Coming soon
Special case n = 1: no two identical chars adjacent; greedy on the most frequent char.
Task Scheduler II
Coming soon
Per-task cooldown via a hashmap of next-available times — a streaming variant.
Single-Threaded CPU
Coming soon
Heap by processing time with availability ordering — richer scheduling with a min-heap.

Same pattern

←

K Closest Points to Origin

Continue · Next problem

Merge k Sorted Lists