Task Scheduler

1. Problem & Core Objective

Given a list of CPU tasks (labelled A–Z) and a cooldown n, return the minimum number of intervals needed to finish them. The same task must be separated by at least n intervals; the CPU may idle.

tasks = ["A","A","A","B","B","B"], n = 2
→ 8        A B idle A B idle A B

tasks = ["A","A","A","B","B","B"], n = 0
→ 6        no cooldown, so no idling

Constraints: 1 <= tasks.length <= 10^4 · tasks are uppercase letters · 0 <= n <= 100

What's actually being tested: whether you see that only the most frequent task matters. The greedy heap simulation works and is what most people write; the O(n) counting formula is what shows you understood why it works. The problem is in the heap section because the simulation is the natural first answer — but the real insight isn't about heaps at all.

2. First-Principles Thought Process

The bottleneck is the most frequent task

Suppose A appears f times. Between consecutive As there must be at least n other intervals. So the As alone force a skeleton:

A _ _ _ A _ _ _ A          f = 3, n = 3

That's f − 1 gaps, each of length n, plus the As themselves. Everything else either fills those gaps or extends past the last A.

No arrangement can be shorter than that skeleton, because the As cannot be packed tighter. That's a genuine lower bound, not a heuristic.

The formula

Think of it as f − 1 frames of width n + 1 (one slot for A, then n slots of cooldown), followed by a tail:

(maxFreq − 1) × (n + 1) + countOfMaxFreq

The tail holds one slot for every task tied for most frequent — with A A A B B B and n = 2, both A and B appear 3 times, so the last frame holds both and the total is 2 × 3 + 2 = 8.

Why the max with tasks.length

The formula counts frame slots, including idles. But with many distinct tasks the gaps fill completely and no idling is needed — then the answer is simply the number of tasks.

A A A B C D E F G H, n = 2
formula: (3−1) × 3 + 1 = 7
reality: 10 tasks, no idle possible → 10

The formula undercounts there, so:

return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countOfMaxFreq);

Why frequencies are all you need

Notice what the formula never uses: the order of the tasks, or which letters they are. Only the frequency distribution — and really only the maximum frequency and how many tasks tie for it.

That's the insight. The rest is arithmetic.

3. Solution Paths

Approach 1 — Greedy simulation with a max-heap

public int leastInterval(char[] tasks, int n) {
    int[] counts = new int[26];
    for (char t : tasks) counts[t - 'A']++;

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int c : counts) if (c > 0) maxHeap.offer(c);

    int time = 0;
    Queue<int[]> cooling = new ArrayDeque<>();      // {remainingCount, readyAtTime}

    while (!maxHeap.isEmpty() || !cooling.isEmpty()) {
        time++;

        if (!maxHeap.isEmpty()) {
            int remaining = maxHeap.poll() - 1;      // run the most frequent available
            if (remaining > 0) cooling.offer(new int[]{remaining, time + n});
        }
        // anything whose cooldown has expired returns to the heap
        if (!cooling.isEmpty() && cooling.peek()[1] == time)
            maxHeap.offer(cooling.poll()[0]);
    }
    return time;
}

• Time O(total intervals × log 26) · Space O(26)

Counter-questions on this approach

⭐ "Why is 'always run the most frequent available' the right greedy choice?"

Because the most frequent task is the bottleneck — it needs the most spacing, so deferring it can only push the finish later. Running it at the earliest legal moment keeps its copies as tightly packed as the cooldown allows, and every other task has more slack.

Formally: the schedule length is bounded below by the most frequent task's skeleton, and this greedy achieves that bound whenever it's achievable. It's a genuine exchange argument, not just intuition.

⭐ "What's the actual running time? log 26 looks like a constant."

It is — at most 26 distinct tasks, so each heap operation is O(log 26) ≈ 5. The real cost is the number of intervals simulated, which is the answer itself.

That's the problem: the answer can be far larger than the input. With one task repeated 10 times and n = 100, the answer is 901 intervals — so the loop runs 901 times for 10 tasks. At the limits, maxFreq up to 10^4 and n = 100 gives roughly 10^6 iterations. It passes, but it's doing work proportional to the output, not the input.

The formula computes the same number in O(total tasks) without simulating anything.

"Why a queue for cooling rather than a second heap?"

Because tasks enter cooling in increasing order of ready-time — each is time + n and time only increases — so the queue is already sorted. A heap would be O(log 26) per operation for ordering I get for free.

"Why check cooling.peek()[1] == time rather than <= time?"

Because exactly one task enters cooling per interval, and each becomes ready exactly n intervals later, so ready-times are distinct and hit exactly. <= would be more defensive and equally correct, and with a while loop instead of if it would handle any timing model. I'd prefer while (... <= time) in production for robustness.

"Is the simulation ever preferable?"

Yes — if you need the actual schedule, not just its length. The formula gives a number; the simulation gives the sequence. That's the honest reason to keep it.

Approach 2 — The counting formula (optimal)

public int leastInterval(char[] tasks, int n) {
    int[] counts = new int[26];
    for (char t : tasks) counts[t - 'A']++;

    int maxFreq = 0;
    for (int c : counts) maxFreq = Math.max(maxFreq, c);

    int countOfMax = 0;
    for (int c : counts) if (c == maxFreq) countOfMax++;

    int frames = (maxFreq - 1) * (n + 1) + countOfMax;
    return Math.max(tasks.length, frames);
}

Trace — A A A B B B, n = 2:

Trace — A A A B C D E F G H, n = 2:

• Time O(total tasks + 26) · Space O(26)

Counter-questions on this approach

⭐ "Derive (maxFreq − 1) × (n + 1) + countOfMax."

Take the most frequent task, appearing f times. Between consecutive copies there must be at least n other intervals, so each copy plus its cooldown occupies n + 1 slots — a frame.

The first f − 1 copies each need a full frame: (f − 1) × (n + 1). The last copy needs no cooldown after it, so it contributes just its own slot.

But every task tied at frequency f has the same structure and its final copy also lands in that last position. So the tail holds countOfMax slots, not 1.

That gives (f − 1)(n + 1) + countOfMax.

⭐ "Why is the max with tasks.length needed? Give an input where the formula is wrong alone."

A A A B C D E F G H with n = 2. The formula gives (3−1) × 3 + 1 = 7, but there are 10 tasks and each occupies an interval — you can't finish 10 tasks in 7 intervals.

What happens is that the extra tasks fill the idle slots and then overflow past the frames. Once the gaps are saturated, no idling occurs at all and the answer is just the task count.

So the formula is a lower bound from the bottleneck, and tasks.length is a lower bound from the total work. The answer is the larger, and both bounds are achievable.

⭐ "Why does countOfMax count tasks tied at the max, rather than something else?"

Because in the final frame, every task with maximum frequency must appear once — they all have a copy remaining after f − 1 frames. They can be placed consecutively since each is a different task and no cooldown applies between different tasks.

With A A A B B B and n = 2, the tail is A B, so 2 slots. If only A were at frequency 3, the tail would be 1 slot.

"Does the order of tasks in the input matter?"

No, and that's the key realisation. The formula uses only the frequency distribution — actually only maxFreq and countOfMax. Any permutation of the same multiset gives the same answer, which is why counting beats simulating.

"What if n = 0?"

Frames become (f − 1) × 1 + countOfMax, which is at most tasks.length, so the max returns tasks.length — correct, since with no cooldown you just run everything back to back. Worth checking rather than assuming the formula degrades gracefully.

"Can maxFreq − 1 be negative?"

Only if maxFreq were 0, meaning no tasks — but the constraint guarantees at least one. With maxFreq = 1 it's 0 × (n+1) + countOfMax = countOfMax = tasks.length, which is right: all tasks distinct, no cooldown needed.

Comparison

4. Why the Optimal Wins

The simulation does work proportional to the answer, which can be far larger than the input — one task repeated 10 times with n = 100 means 901 iterations for 10 tasks. The formula computes the same number directly from the frequency counts.

The deeper point is what the formula reveals: the answer depends on only two numbers — the maximum frequency and how many tasks tie for it. Not the order, not the other frequencies, not even how many distinct tasks there are except through tasks.length.

The framing worth keeping:

The most frequent task sets a skeleton that nothing can compress: f − 1 frames of width n + 1, plus a tail for every task tied at f. The answer is that, or the task count, whichever is larger.

5. Java Prerequisites

Frequency counting over a fixed alphabet

int[] counts = new int[26];
for (char t : tasks) counts[t - 'A']++;

Uppercase here, so - 'A'. Lowercase problems use - 'a'.

The formula

int frames = (maxFreq - 1) * (n + 1) + countOfMax;
return Math.max(tasks.length, frames);

Overflow check. maxFreq <= 10^4 and n <= 100, so frames <= 10^4 × 101 ≈ 10^6 — int is ample.

ArrayDeque as a FIFO queue — offer/poll/peek. Faster than LinkedList and forbids nulls.

6. Interview Communication Guide

Clarifying questions: Must the cooldown be at least n, or exactly n (at least)? Can the CPU idle (yes — that's what creates the gaps)? Do I need the schedule or just its length (just the length; it decides formula vs simulation)? Are tasks always A–Z (yes, so 26 buckets)?

The pitch

"The insight is that only the most frequent task matters.

Say the most frequent task appears f times. Between consecutive copies there must be at least n other intervals, so those copies alone force a skeleton: f − 1 frames of width n + 1, then a final copy. Nothing can compress that, so it's a genuine lower bound.

The tail isn't one slot though — every task tied at frequency f also has a final copy landing there, and different tasks need no cooldown between them. So the tail is countOfMax slots.

That gives (maxFreq − 1) × (n + 1) + countOfMax.

One correction is needed. With many distinct tasks the gaps fill completely and overflow, so no idling happens and the answer is just the number of tasks. The formula undercounts there — A A A B C D E F G H with n = 2 gives 7, but there are 10 tasks. So the answer is max(tasks.length, frames): one bound from the bottleneck, one from the total work, and both are achievable.

That's O(tasks) with a 26-element count array.

The alternative is a greedy simulation with a max-heap — always run the most frequent available task, with a queue holding those on cooldown. It's correct and it's the natural first answer, but it does work proportional to the answer rather than the input: one task repeated 10 times with n = 100 means 901 iterations for 10 tasks.

I'd mention the simulation is the right choice if you need the actual schedule rather than just its length."

Edge cases to volunteer:

Name the n = 0 case and the overflow case. The first checks the formula degrades correctly; the second is the only reason the max exists, and a solution without it passes most tests.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the actual schedule, not just its length."

Now the simulation is required — the formula gives a count, not an assignment. Run the greedy heap version and record which task fires in each interval, emitting idle when the heap is empty but cooling isn't. O(answer) time, which is unavoidable since the output is that long.

⭐ "Different tasks have different cooldowns."

The formula collapses — it assumes a single n shared by all tasks, so the frame width is no longer uniform. You'd fall back to the greedy simulation with a per-task ready-time, and even then "run the most frequent available" is no longer provably optimal. This is where a clean closed form stops existing, and saying so is better than improvising one.

"Tasks have priorities and must respect a partial order."

That's topological scheduling with cooldown constraints — closer to job-shop scheduling, which is NP-hard in general. Heuristics like list scheduling apply. Worth naming the complexity class rather than pretending the greedy extends.

"What if there were more than 26 task types?"

Replace the 26-array with a HashMap<String, Integer>. Nothing else changes — the formula never uses the alphabet size, only maxFreq and countOfMax. That it survives this change unchanged is evidence the formula captured the right thing.

"Minimise idle time rather than total time."

They're equivalent: idle = totalTime − tasks.length, and tasks.length is fixed. So minimising one minimises the other. Worth noticing, because it means the answer is already optimal for both objectives.

"What if n could be up to 10^9?"

The formula is unaffected — it's arithmetic, so O(tasks) regardless of n. But the simulation becomes impossible: (maxFreq − 1) × (n + 1) intervals could be 10^13. That's the clearest demonstration of why computing beats simulating here.