DSA-076 · Frequency frame bound with an eligibility-aware construction

Task Scheduler with Cooldown

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 3530 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the minimum number of unit time slots needed to execute every task occurrence, with at least cooldown other slots between equal task labels. Tasks use the fixed uppercase A..Z alphabet. Return a length, not a materialized schedule.

tasks is nonnull with at most 100,000 uppercase A..Z characters. cooldown is a nonnegative int. Null throws NullPointerException; a negative cooldown or any other character throws IllegalArgumentException. Validation does not modify input.
Tasks all take one slot and share the same cooldown; idle slots are permitted. A task run at time t may next run at t+cooldown+1. Empty tasks return 0, and cooldown=0 returns the task count.
Return long because up to (n−1)*(cooldown+1)+1 slots can exceed int. The optimized method computes only length. The baseline simulate helper constructs executions internally using a ready heap/cooldown queue and jumps over idle ranges, storing no expanded idle string. Trace blocks are illustrative history, excluded from Java’s state bound.

Examples

Input: tasks=AAABBB, cooldown=2
Output: 8
One optimum is A,B,idle,A,B,idle,A,B. Equal labels start three slots apart.
Input: tasks=ABCABC, cooldown=0
Output: 6
All occurrences fit without idle slots; workload count dominates any frame bound.
Input: tasks=AAA, cooldown=MAX
Output: 4,294,967,297
Two huge cooldown gaps are represented by long arithmetic and compressed idle blocks, not billions of loop iterations.
Input: tasks=[], cooldown=0
Output: 0
No maximum-frequency frame is needed.

Before you start

Uniform unit-time cooldown scheduling
Frequency maxima, tied maxima, and long arithmetic

Recognize the structure

For uniform unit tasks, only label frequencies determine the minimum length. The most frequent labels impose spacing, while total work imposes another lower bound. Actual reconstruction needs eligibility state; a max-heap of counts alone must not immediately rerun a cooling task.

Try before revealing

Hint 1

What independent lower bounds come from total work and the most frequent labels?

Hint 2

Count all labels tied at the largest frequency, not only one anchor.

Hint 3

Compute max(n,(f−1)*(c+1)+t) in long; use eligibility-aware simulation only when constructing a witness.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Greedy ready heap plus cooldown queue

At each event time release every label whose availableAt has arrived, run the eligible label with greatest remaining count (alphabetical ties), and enqueue it with its next legal time if work remains. If none is eligible, jump to the earliest release. For AAABBB,c=2, runs occur at 0,1,3,4,6,7 with idle intervals [2,3) and [5,6), finishing at time 8. The helper simulate returns that length; it does not allocate a full schedule. Fixed cooldown makes release times FIFO because execution times increase.

Improve the baseline

Count dominant repetitions and ties

Let f be the maximum frequency and t the number of labels occurring f times. Empty input is handled before this count can confuse unused zero-frequency labels with real tasks.

Build two lower bounds

Every occurrence needs a slot, giving n. The f repetitions of each maximally frequent label require f−1 separating frames of width at least c+1; all t final tied occurrences must also fit, giving (f−1)*(c+1)+t.

Use the tight combined bound

The answer is max(n,frame). Frequency-round construction can attain that bound: process at most c+1 distinct largest remaining labels per round, preserving consistent tie order, pad only nonfinal short rounds, and omit padding after the final work. The simulation offers an explicit eligibility-aware witness for the same length.

Why it is correct

Lower bounds

A machine executes at most one task per slot, so length>=n. Among the t labels with frequency f, the first of their final occurrences cannot precede (f−1)*(c+1); the last of those t distinct final occurrences is at least t−1 slots later. Therefore length>=(f−1)*(c+1)+t.

Valid attaining construction

Use rounds of length L=c+1, selecting the largest remaining counts, at most one of each label per round. A label surviving into the next round cannot move to an earlier position: selected counts all decrease equally, earlier surviving selected labels keep their rank, and newly competitive unselected labels can only push it later. Skipping a round only increases separation. Thus repeated starts are at least L apart; final-round padding is unnecessary.

Why the construction reaches the bound

For a nonfinal full round, subtract one from the top L counts. The expression max(n,(f−1)*L+t) decreases by L: if more than L maxima tie, t decreases by L; otherwise maxima drop a level, and any additional next-level ties imply enough remaining work for n to dominate. A short nonfinal round contains all remaining labels; f drops by one with the same maximally frequent ties, so the frame bound decreases by L. When all remaining counts equal one, the last round takes exactly their count. Inducting over rounds gives the claimed length, matching both lower bounds.

Simulation eligibility and numeric safety

The ready heap contains only runnable labels; waiting stores future releases in increasing order. After executing [time,time+1), next legal time is the incremented time+cooldown. Jumping when ready is empty skips only forced idle slots. All arithmetic widens before multiplication/addition; under the declared size bound the result fits long.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;
public final class Solution {
    private record Job(char task, int remaining) {}
    private record Waiting(Job job, long availableAt) {}
    private static int[] frequencies(char[] tasks, int cooldown) {
        Objects.requireNonNull(tasks, "tasks");
        if (cooldown < 0) throw new IllegalArgumentException("negative cooldown");
        int[] frequency = new int[26];
        for (char task : tasks) {
            if (task < 'A' || task > 'Z') throw new IllegalArgumentException("task outside A..Z");
            frequency[task-'A']++;
        }
        return frequency;
    }
    public static long leastInterval(char[] tasks, int cooldown) {
        int[] frequency = frequencies(tasks,cooldown);
        if (tasks.length == 0) return 0;
        int maximum = 0, tied = 0;
        for (int count : frequency) {
            if (count > maximum) { maximum = count; tied = 1; }
            else if (count == maximum) tied++;
        }
        long frame = (maximum - 1L) * (cooldown + 1L) + tied;
        return Math.max(tasks.length,frame);
    }
    public static long simulate(char[] tasks, int cooldown) {
        int[] frequency = frequencies(tasks,cooldown);
        PriorityQueue<Job> ready = new PriorityQueue<>(Comparator.comparingInt(Job::remaining).reversed().thenComparingInt(Job::task));
        ArrayDeque<Waiting> waiting = new ArrayDeque<>();
        for (int i = 0; i < 26; i++) if (frequency[i] > 0) ready.offer(new Job((char) ('A'+i),frequency[i]));
        long time = 0;
        while (!ready.isEmpty() || !waiting.isEmpty()) {
            while (!waiting.isEmpty() && waiting.peekFirst().availableAt <= time) ready.offer(waiting.removeFirst().job);
            if (ready.isEmpty()) { time = waiting.peekFirst().availableAt; continue; }
            Job chosen = ready.poll();
            time++;
            if (chosen.remaining > 1) waiting.addLast(new Waiting(new Job(chosen.task,chosen.remaining-1),time+cooldown));
        }
        return time;
    }
    public static long baseline(char[] tasks, int cooldown) { return simulate(tasks,cooldown); }
}

Read the meaningful blocks

Guard empty before frames

Return zero before interpreting maximum/tied counters on an all-zero frequency array.

Widen both factors

(maximum−1L)*(cooldown+1L)+tied prevents overflow in cooldown+1 before multiplication and in the final length.

Release, choose, cool down

The baseline first releases all eligible jobs, then selects the highest remaining ready count. Waiting labels are not treated as runnable even if their count is largest.

Jump, do not emit idle characters

A long cooldown changes event timestamps but not the number of executions. Compressed walkthrough idle intervals represent the gap without changing Java’s space cost.

Complexity

With fixed alphabet σ=26, optimized time is O(n+σ) and auxiliary storage O(σ); returned output is one long. Counting and validation scan the input once, and frame arithmetic is constant work.

The event-driven baseline uses O(n log(σ+1)) time and O(σ) ready/waiting state, independent of the expanded idle length. A slot-by-slot simulation or a literal returned schedule would cost at least the schedule length, which can be enormous.

Exact-state walkthroughs

Reveal normal and boundary traces

Tied dominant tasks require forced idle

Input: {"tasks":"AAABBB","cooldown":2} · Minimum slot count: 8

Step 1 of 14: Compute the work and frequency-frame bounds; reconstruct by events.

The optimized Java method returns only minimum length; ready/waiting state below illustrates the constructive simulate helper.

Cooldown scheduling — eligible work and compressed idle gaps

Phase: initial. Time boundary: 0. Cooldown: 2. Work bound: 6; frequency-frame bound: 8; minimum length: 8.

Ready labels — remaining count descending

A: 3 left
B: 3 left

Pending releases — next legal start times

Empty.

Illustrative history — exact half-open run/idle intervals

Empty.

A pending release can become eligible at the displayed time and moves to ready when the release loop runs. Idle blocks are compressed, not drawn to duration scale. Java returns only a long length and does not retain this teaching history.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
tasks	`"AAABBB"`
cooldown	`2`
frequencies	`[["A",3],["B",3]]`
maximum	`3`
tied	`2`
frame	`8`
minimum	`8`
time	`0`
ready	`[{"task":"A","remaining":3},{"task":"B","remaining":3}]`
waiting	`[]`
blocks	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     private record Job(char task, int remaining) {}
 7     private record Waiting(Job job, long availableAt) {}
 8     private static int[] frequencies(char[] tasks, int cooldown) {
 9         Objects.requireNonNull(tasks, "tasks");
10         if (cooldown < 0) throw new IllegalArgumentException("negative cooldown");
11         int[] frequency = new int[26];
12         for (char task : tasks) {
13             if (task < 'A' || task > 'Z') throw new IllegalArgumentException("task outside A..Z");
14             frequency[task-'A']++;
15         }
16         return frequency;
17     }
18     public static long leastInterval(char[] tasks, int cooldown) {
19         int[] frequency = frequencies(tasks,cooldown);
20         if (tasks.length == 0) return 0;
21         int maximum = 0, tied = 0;
22         for (int count : frequency) {
23             if (count > maximum) { maximum = count; tied = 1; }
24             else if (count == maximum) tied++;
25         }
26         long frame = (maximum - 1L) * (cooldown + 1L) + tied;
27         return Math.max(tasks.length,frame);
28     }
29     public static long simulate(char[] tasks, int cooldown) {
30         int[] frequency = frequencies(tasks,cooldown);
31         PriorityQueue<Job> ready = new PriorityQueue<>(Comparator.comparingInt(Job::remaining).reversed().thenComparingInt(Job::task));
32         ArrayDeque<Waiting> waiting = new ArrayDeque<>();
33         for (int i = 0; i < 26; i++) if (frequency[i] > 0) ready.offer(new Job((char) ('A'+i),frequency[i]));
34         long time = 0;
35         while (!ready.isEmpty() || !waiting.isEmpty()) {
36             while (!waiting.isEmpty() && waiting.peekFirst().availableAt <= time) ready.offer(waiting.removeFirst().job);
37             if (ready.isEmpty()) { time = waiting.peekFirst().availableAt; continue; }
38             Job chosen = ready.poll();
39             time++;
40             if (chosen.remaining > 1) waiting.addLast(new Waiting(new Job(chosen.task,chosen.remaining-1),time+cooldown));
41         }
42         return time;
43     }
44     public static long baseline(char[] tasks, int cooldown) { return simulate(tasks,cooldown); }
45 }
46

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Compute the work and frequency-frame bounds; reconstruct by events.
The optimized Java method returns only minimum length; ready/waiting state below illustrates the constructive simulate helper.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
0
ready
[{"task":"A","remaining":3},{"task":"B","remaining":3}]
waiting
[]
blocks
[]
phase
"initial"
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
1
ready
[{"task":"B","remaining":3}]
waiting
[{"task":"A","remaining":2,"availableAt":3}]
blocks
[{"task":"A","start":0,"end":1}]
phase
"run"
chosen
{"task":"A","remaining":3}
start
0
end
1
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
2
ready
[]
waiting
[{"task":"A","remaining":2,"availableAt":3},{"task":"B","remaining":2,"availableAt":4}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2}]
phase
"run"
chosen
{"task":"B","remaining":3}
start
1
end
2
Jump over a forced idle interval without expanding its slots.
No label is runnable during this gap. A compressed [start,end) block is history for teaching, not a Java output array.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
3
ready
[]
waiting
[{"task":"A","remaining":2,"availableAt":3},{"task":"B","remaining":2,"availableAt":4}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3}]
phase
"idle"
start
2
end
3
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
3
ready
[{"task":"A","remaining":2}]
waiting
[{"task":"B","remaining":2,"availableAt":4}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3}]
phase
"release"
released
{"task":"A","remaining":2,"availableAt":3}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
4
ready
[]
waiting
[{"task":"B","remaining":2,"availableAt":4},{"task":"A","remaining":1,"availableAt":6}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3},{"task":"A","start":3,"end":4}]
phase
"run"
chosen
{"task":"A","remaining":2}
start
3
end
4
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
4
ready
[{"task":"B","remaining":2}]
waiting
[{"task":"A","remaining":1,"availableAt":6}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3},{"task":"A","start":3,"end":4}]
phase
"release"
released
{"task":"B","remaining":2,"availableAt":4}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
5
ready
[]
waiting
[{"task":"A","remaining":1,"availableAt":6},{"task":"B","remaining":1,"availableAt":7}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3},{"task":"A","start":3,"end":4},{"task":"B","start":4,"end":5}]
phase
"run"
chosen
{"task":"B","remaining":2}
start
4
end
5
Jump over a forced idle interval without expanding its slots.
No label is runnable during this gap. A compressed [start,end) block is history for teaching, not a Java output array.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
6
ready
[]
waiting
[{"task":"A","remaining":1,"availableAt":6},{"task":"B","remaining":1,"availableAt":7}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3},{"task":"A","start":3,"end":4},{"task":"B","start":4,"end":5},{"task":"idle","start":5,"end":6}]
phase
"idle"
start
5
end
6
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
6
ready
[{"task":"A","remaining":1}]
waiting
[{"task":"B","remaining":1,"availableAt":7}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3},{"task":"A","start":3,"end":4},{"task":"B","start":4,"end":5},{"task":"idle","start":5,"end":6}]
phase
"release"
released
{"task":"A","remaining":1,"availableAt":6}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
7
ready
[]
waiting
[{"task":"B","remaining":1,"availableAt":7}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3},{"task":"A","start":3,"end":4},{"task":"B","start":4,"end":5},{"task":"idle","start":5,"end":6},{"task":"A","start":6,"end":7}]
phase
"run"
chosen
{"task":"A","remaining":1}
start
6
end
7
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
7
ready
[{"task":"B","remaining":1}]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3},{"task":"A","start":3,"end":4},{"task":"B","start":4,"end":5},{"task":"idle","start":5,"end":6},{"task":"A","start":6,"end":7}]
phase
"release"
released
{"task":"B","remaining":1,"availableAt":7}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAABBB"
cooldown
2
frequencies
[["A",3],["B",3]]
maximum
3
tied
2
frame
8
minimum
8
time
8
ready
[]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"idle","start":2,"end":3},{"task":"A","start":3,"end":4},{"task":"B","start":4,"end":5},{"task":"idle","start":5,"end":6},{"task":"A","start":6,"end":7},{"task":"B","start":7,"end":8}]
phase
"run"
chosen
{"task":"B","remaining":1}
start
7
end
8
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
8

Zero cooldown has no forced idle

Input: {"tasks":"ABCABC","cooldown":0} · Minimum slot count: 6

Step 1 of 11: Compute the work and frequency-frame bounds; reconstruct by events.

The optimized Java method returns only minimum length; ready/waiting state below illustrates the constructive simulate helper.

Cooldown scheduling — eligible work and compressed idle gaps

Phase: initial. Time boundary: 0. Cooldown: 0. Work bound: 6; frequency-frame bound: 4; minimum length: 6.

Ready labels — remaining count descending

A: 2 left
B: 2 left
C: 2 left

Pending releases — next legal start times

Empty.

Illustrative history — exact half-open run/idle intervals

Empty.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
tasks	`"ABCABC"`
cooldown	`0`
frequencies	`[["A",2],["B",2],["C",2]]`
maximum	`2`
tied	`3`
frame	`4`
minimum	`6`
time	`0`
ready	`[{"task":"A","remaining":2},{"task":"B","remaining":2},{"task":"C","remaining":2}]`
waiting	`[]`
blocks	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     private record Job(char task, int remaining) {}
 7     private record Waiting(Job job, long availableAt) {}
 8     private static int[] frequencies(char[] tasks, int cooldown) {
 9         Objects.requireNonNull(tasks, "tasks");
10         if (cooldown < 0) throw new IllegalArgumentException("negative cooldown");
11         int[] frequency = new int[26];
12         for (char task : tasks) {
13             if (task < 'A' || task > 'Z') throw new IllegalArgumentException("task outside A..Z");
14             frequency[task-'A']++;
15         }
16         return frequency;
17     }
18     public static long leastInterval(char[] tasks, int cooldown) {
19         int[] frequency = frequencies(tasks,cooldown);
20         if (tasks.length == 0) return 0;
21         int maximum = 0, tied = 0;
22         for (int count : frequency) {
23             if (count > maximum) { maximum = count; tied = 1; }
24             else if (count == maximum) tied++;
25         }
26         long frame = (maximum - 1L) * (cooldown + 1L) + tied;
27         return Math.max(tasks.length,frame);
28     }
29     public static long simulate(char[] tasks, int cooldown) {
30         int[] frequency = frequencies(tasks,cooldown);
31         PriorityQueue<Job> ready = new PriorityQueue<>(Comparator.comparingInt(Job::remaining).reversed().thenComparingInt(Job::task));
32         ArrayDeque<Waiting> waiting = new ArrayDeque<>();
33         for (int i = 0; i < 26; i++) if (frequency[i] > 0) ready.offer(new Job((char) ('A'+i),frequency[i]));
34         long time = 0;
35         while (!ready.isEmpty() || !waiting.isEmpty()) {
36             while (!waiting.isEmpty() && waiting.peekFirst().availableAt <= time) ready.offer(waiting.removeFirst().job);
37             if (ready.isEmpty()) { time = waiting.peekFirst().availableAt; continue; }
38             Job chosen = ready.poll();
39             time++;
40             if (chosen.remaining > 1) waiting.addLast(new Waiting(new Job(chosen.task,chosen.remaining-1),time+cooldown));
41         }
42         return time;
43     }
44     public static long baseline(char[] tasks, int cooldown) { return simulate(tasks,cooldown); }
45 }
46

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Compute the work and frequency-frame bounds; reconstruct by events.
The optimized Java method returns only minimum length; ready/waiting state below illustrates the constructive simulate helper.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
0
ready
[{"task":"A","remaining":2},{"task":"B","remaining":2},{"task":"C","remaining":2}]
waiting
[]
blocks
[]
phase
"initial"
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
1
ready
[{"task":"B","remaining":2},{"task":"C","remaining":2}]
waiting
[{"task":"A","remaining":1,"availableAt":1}]
blocks
[{"task":"A","start":0,"end":1}]
phase
"run"
chosen
{"task":"A","remaining":2}
start
0
end
1
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
1
ready
[{"task":"B","remaining":2},{"task":"C","remaining":2},{"task":"A","remaining":1}]
waiting
[]
blocks
[{"task":"A","start":0,"end":1}]
phase
"release"
released
{"task":"A","remaining":1,"availableAt":1}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
2
ready
[{"task":"C","remaining":2},{"task":"A","remaining":1}]
waiting
[{"task":"B","remaining":1,"availableAt":2}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2}]
phase
"run"
chosen
{"task":"B","remaining":2}
start
1
end
2
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
2
ready
[{"task":"C","remaining":2},{"task":"A","remaining":1},{"task":"B","remaining":1}]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2}]
phase
"release"
released
{"task":"B","remaining":1,"availableAt":2}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
3
ready
[{"task":"A","remaining":1},{"task":"B","remaining":1}]
waiting
[{"task":"C","remaining":1,"availableAt":3}]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"C","start":2,"end":3}]
phase
"run"
chosen
{"task":"C","remaining":2}
start
2
end
3
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
3
ready
[{"task":"A","remaining":1},{"task":"B","remaining":1},{"task":"C","remaining":1}]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"C","start":2,"end":3}]
phase
"release"
released
{"task":"C","remaining":1,"availableAt":3}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
4
ready
[{"task":"B","remaining":1},{"task":"C","remaining":1}]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"C","start":2,"end":3},{"task":"A","start":3,"end":4}]
phase
"run"
chosen
{"task":"A","remaining":1}
start
3
end
4
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
5
ready
[{"task":"C","remaining":1}]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"C","start":2,"end":3},{"task":"A","start":3,"end":4},{"task":"B","start":4,"end":5}]
phase
"run"
chosen
{"task":"B","remaining":1}
start
4
end
5
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"ABCABC"
cooldown
0
frequencies
[["A",2],["B",2],["C",2]]
maximum
2
tied
3
frame
4
minimum
6
time
6
ready
[]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"B","start":1,"end":2},{"task":"C","start":2,"end":3},{"task":"A","start":3,"end":4},{"task":"B","start":4,"end":5},{"task":"C","start":5,"end":6}]
phase
"run"
chosen
{"task":"C","remaining":1}
start
5
end
6
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
6

Huge cooldown jumps are compressed

Input: {"tasks":"AAA","cooldown":2147483647} · Minimum slot count: 4294967297

Step 1 of 9: Compute the work and frequency-frame bounds; reconstruct by events.

The optimized Java method returns only minimum length; ready/waiting state below illustrates the constructive simulate helper.

Cooldown scheduling — eligible work and compressed idle gaps

Phase: initial. Time boundary: 0. Cooldown: 2147483647. Work bound: 3; frequency-frame bound: 4294967297; minimum length: 4294967297.

Ready labels — remaining count descending

A: 3 left

Pending releases — next legal start times

Empty.

Illustrative history — exact half-open run/idle intervals

Empty.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
tasks	`"AAA"`
cooldown	`2147483647`
frequencies	`[["A",3]]`
maximum	`3`
tied	`1`
frame	`4294967297`
minimum	`4294967297`
time	`0`
ready	`[{"task":"A","remaining":3}]`
waiting	`[]`
blocks	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     private record Job(char task, int remaining) {}
 7     private record Waiting(Job job, long availableAt) {}
 8     private static int[] frequencies(char[] tasks, int cooldown) {
 9         Objects.requireNonNull(tasks, "tasks");
10         if (cooldown < 0) throw new IllegalArgumentException("negative cooldown");
11         int[] frequency = new int[26];
12         for (char task : tasks) {
13             if (task < 'A' || task > 'Z') throw new IllegalArgumentException("task outside A..Z");
14             frequency[task-'A']++;
15         }
16         return frequency;
17     }
18     public static long leastInterval(char[] tasks, int cooldown) {
19         int[] frequency = frequencies(tasks,cooldown);
20         if (tasks.length == 0) return 0;
21         int maximum = 0, tied = 0;
22         for (int count : frequency) {
23             if (count > maximum) { maximum = count; tied = 1; }
24             else if (count == maximum) tied++;
25         }
26         long frame = (maximum - 1L) * (cooldown + 1L) + tied;
27         return Math.max(tasks.length,frame);
28     }
29     public static long simulate(char[] tasks, int cooldown) {
30         int[] frequency = frequencies(tasks,cooldown);
31         PriorityQueue<Job> ready = new PriorityQueue<>(Comparator.comparingInt(Job::remaining).reversed().thenComparingInt(Job::task));
32         ArrayDeque<Waiting> waiting = new ArrayDeque<>();
33         for (int i = 0; i < 26; i++) if (frequency[i] > 0) ready.offer(new Job((char) ('A'+i),frequency[i]));
34         long time = 0;
35         while (!ready.isEmpty() || !waiting.isEmpty()) {
36             while (!waiting.isEmpty() && waiting.peekFirst().availableAt <= time) ready.offer(waiting.removeFirst().job);
37             if (ready.isEmpty()) { time = waiting.peekFirst().availableAt; continue; }
38             Job chosen = ready.poll();
39             time++;
40             if (chosen.remaining > 1) waiting.addLast(new Waiting(new Job(chosen.task,chosen.remaining-1),time+cooldown));
41         }
42         return time;
43     }
44     public static long baseline(char[] tasks, int cooldown) { return simulate(tasks,cooldown); }
45 }
46

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Compute the work and frequency-frame bounds; reconstruct by events.
The optimized Java method returns only minimum length; ready/waiting state below illustrates the constructive simulate helper.
tasks
"AAA"
cooldown
2147483647
frequencies
[["A",3]]
maximum
3
tied
1
frame
4294967297
minimum
4294967297
time
0
ready
[{"task":"A","remaining":3}]
waiting
[]
blocks
[]
phase
"initial"
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAA"
cooldown
2147483647
frequencies
[["A",3]]
maximum
3
tied
1
frame
4294967297
minimum
4294967297
time
1
ready
[]
waiting
[{"task":"A","remaining":2,"availableAt":2147483648}]
blocks
[{"task":"A","start":0,"end":1}]
phase
"run"
chosen
{"task":"A","remaining":3}
start
0
end
1
Jump over a forced idle interval without expanding its slots.
No label is runnable during this gap. A compressed [start,end) block is history for teaching, not a Java output array.
tasks
"AAA"
cooldown
2147483647
frequencies
[["A",3]]
maximum
3
tied
1
frame
4294967297
minimum
4294967297
time
2147483648
ready
[]
waiting
[{"task":"A","remaining":2,"availableAt":2147483648}]
blocks
[{"task":"A","start":0,"end":1},{"task":"idle","start":1,"end":2147483648}]
phase
"idle"
start
1
end
2147483648
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"AAA"
cooldown
2147483647
frequencies
[["A",3]]
maximum
3
tied
1
frame
4294967297
minimum
4294967297
time
2147483648
ready
[{"task":"A","remaining":2}]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"idle","start":1,"end":2147483648}]
phase
"release"
released
{"task":"A","remaining":2,"availableAt":2147483648}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAA"
cooldown
2147483647
frequencies
[["A",3]]
maximum
3
tied
1
frame
4294967297
minimum
4294967297
time
2147483649
ready
[]
waiting
[{"task":"A","remaining":1,"availableAt":4294967296}]
blocks
[{"task":"A","start":0,"end":1},{"task":"idle","start":1,"end":2147483648},{"task":"A","start":2147483648,"end":2147483649}]
phase
"run"
chosen
{"task":"A","remaining":2}
start
2147483648
end
2147483649
Jump over a forced idle interval without expanding its slots.
No label is runnable during this gap. A compressed [start,end) block is history for teaching, not a Java output array.
tasks
"AAA"
cooldown
2147483647
frequencies
[["A",3]]
maximum
3
tied
1
frame
4294967297
minimum
4294967297
time
4294967296
ready
[]
waiting
[{"task":"A","remaining":1,"availableAt":4294967296}]
blocks
[{"task":"A","start":0,"end":1},{"task":"idle","start":1,"end":2147483648},{"task":"A","start":2147483648,"end":2147483649},{"task":"idle","start":2147483649,"end":4294967296}]
phase
"idle"
start
2147483649
end
4294967296
Release one now-eligible label before choosing work.
Waiting is FIFO because all tasks have the same cooldown and prior execution times increase.
tasks
"AAA"
cooldown
2147483647
frequencies
[["A",3]]
maximum
3
tied
1
frame
4294967297
minimum
4294967297
time
4294967296
ready
[{"task":"A","remaining":1}]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"idle","start":1,"end":2147483648},{"task":"A","start":2147483648,"end":2147483649},{"task":"idle","start":2147483649,"end":4294967296}]
phase
"release"
released
{"task":"A","remaining":1,"availableAt":4294967296}
Execute one eligible unit and cool it down if work remains.
After incrementing time, next legal start is time+cooldown. Ready contains only other eligible labels; a cooling label cannot be selected early.
tasks
"AAA"
cooldown
2147483647
frequencies
[["A",3]]
maximum
3
tied
1
frame
4294967297
minimum
4294967297
time
4294967297
ready
[]
waiting
[]
blocks
[{"task":"A","start":0,"end":1},{"task":"idle","start":1,"end":2147483648},{"task":"A","start":2147483648,"end":2147483649},{"task":"idle","start":2147483649,"end":4294967296},{"task":"A","start":4294967296,"end":4294967297}]
phase
"run"
chosen
{"task":"A","remaining":1}
start
4294967296
end
4294967297
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
4294967297

Empty task set

Input: {"tasks":"","cooldown":0} · Minimum slot count: 0

Step 1 of 2: Compute the work and frequency-frame bounds; reconstruct by events.

The optimized Java method returns only minimum length; ready/waiting state below illustrates the constructive simulate helper.

Cooldown scheduling — eligible work and compressed idle gaps

Phase: initial. Time boundary: 0. Cooldown: 0. Work bound: 0; frequency-frame bound: 0; minimum length: 0.

Ready labels — remaining count descending

Empty.

Pending releases — next legal start times

Empty.

Illustrative history — exact half-open run/idle intervals

Empty.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
tasks	`""`
cooldown	`0`
frequencies	`[]`
maximum	`0`
tied	`0`
frame	`0`
minimum	`0`
time	`0`
ready	`[]`
waiting	`[]`
blocks	`[]`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     private record Job(char task, int remaining) {}
 7     private record Waiting(Job job, long availableAt) {}
 8     private static int[] frequencies(char[] tasks, int cooldown) {
 9         Objects.requireNonNull(tasks, "tasks");
10         if (cooldown < 0) throw new IllegalArgumentException("negative cooldown");
11         int[] frequency = new int[26];
12         for (char task : tasks) {
13             if (task < 'A' || task > 'Z') throw new IllegalArgumentException("task outside A..Z");
14             frequency[task-'A']++;
15         }
16         return frequency;
17     }
18     public static long leastInterval(char[] tasks, int cooldown) {
19         int[] frequency = frequencies(tasks,cooldown);
20         if (tasks.length == 0) return 0;
21         int maximum = 0, tied = 0;
22         for (int count : frequency) {
23             if (count > maximum) { maximum = count; tied = 1; }
24             else if (count == maximum) tied++;
25         }
26         long frame = (maximum - 1L) * (cooldown + 1L) + tied;
27         return Math.max(tasks.length,frame);
28     }
29     public static long simulate(char[] tasks, int cooldown) {
30         int[] frequency = frequencies(tasks,cooldown);
31         PriorityQueue<Job> ready = new PriorityQueue<>(Comparator.comparingInt(Job::remaining).reversed().thenComparingInt(Job::task));
32         ArrayDeque<Waiting> waiting = new ArrayDeque<>();
33         for (int i = 0; i < 26; i++) if (frequency[i] > 0) ready.offer(new Job((char) ('A'+i),frequency[i]));
34         long time = 0;
35         while (!ready.isEmpty() || !waiting.isEmpty()) {
36             while (!waiting.isEmpty() && waiting.peekFirst().availableAt <= time) ready.offer(waiting.removeFirst().job);
37             if (ready.isEmpty()) { time = waiting.peekFirst().availableAt; continue; }
38             Job chosen = ready.poll();
39             time++;
40             if (chosen.remaining > 1) waiting.addLast(new Waiting(new Job(chosen.task,chosen.remaining-1),time+cooldown));
41         }
42         return time;
43     }
44     public static long baseline(char[] tasks, int cooldown) { return simulate(tasks,cooldown); }
45 }
46

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Compute the work and frequency-frame bounds; reconstruct by events.
The optimized Java method returns only minimum length; ready/waiting state below illustrates the constructive simulate helper.
tasks
""
cooldown
0
frequencies
[]
maximum
0
tied
0
frame
0
minimum
0
time
0
ready
[]
waiting
[]
blocks
[]
phase
"initial"
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
0

Test the contract

Input: AAABBB,c=2
Output: 8
Tied maxima and forced idle.
Input: ABCABC,c=0
Output: 6
Workload dominates.
Input: AAA,c=MAX
Output: 4,294,967,297
Long length and idle jumps.
Input: All counts 0..3 on A/B/C, c=0..3
Output: Exact state-space optimum
Independent bounded exhaustive scheduling oracle.
Input: Lowercase/digit/NUL or negative cooldown
Output: IllegalArgumentException
Explicit task alphabet and timing contract.

Common mistakes and counterexamples

Forget the workload lower bound

Counterexample: With many distinct labels and c=0, a small maximum frequency does not reduce the n required executions.

Return max(n,frame).

Forget tied maximum labels

Counterexample: AAABBB,c=2 needs eight slots; (f−1)*(c+1)+1 gives only seven.

Add t, the number of maximum-frequency labels.

Make a task available after only c positions between starts

Counterexample: At c=2, starts at 0 and 2 have only one intervening slot.

Next start is previous start+c+1.

Iterate billions of idle units

Counterexample: AAA,c=MAX is a tiny event sequence with a huge elapsed length.

Jump to the earliest eligibility timestamp and represent idle gaps compactly.

Reuse the formula for different durations/cooldowns

Counterexample: Per-label cooldowns or nonunit durations break the frequency-frame model.

Redefine feasibility and use a separately justified scheduler.

Follow-ups

Return an actual schedule.

Return compressed run/idle intervals or impose an output-length cap. Verify every occurrence and label separation; a long minimum length does not imply a manageable expanded string.

Use different per-label cooldowns.

FIFO release ordering and the single frame formula no longer follow. A release-time min-heap may help simulate eligibility, but optimality needs a new scheduling proof.

Tasks have nonunit durations or dependencies.

Frequency alone no longer determines the optimum. Model finish times, release constraints, and precedence explicitly rather than treating this formula as a general job scheduler.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 140/20,000 characters

Self-review

I prove both bounds and a valid attaining construction.I distinguish length-only arithmetic from reconstruction history.I track exact release times, tied maxima, and widened arithmetic.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Heaps: retain the useful frontier

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external platform-difficulty claims.