A worker pool runs labeled job types — retry storms, cache warmers, report dumps — and two jobs of the same type cannot share a slot until at least n other slots have passed. Idle is allowed; the SLA still counts wall time. The intern version walked remaining counts every tick looking for a type that was free. A dozen mixed jobs finished before standup. A burst of one hot type with n = 3 was still scanning leftovers while the pool sat idle for half the window.

Task Scheduler asks for the fewest slots that finish every task under that cooldown. A heap already gives the next-busiest remaining count at the root. Rescanning leftovers each slot uses that answer and still pays a full walk per tick.

This is an interview writeup, not a heap lecture. That post owns sift. Java’s PriorityQueue is a min-heap. Invert it so poll is the largest remaining count. Last Stone Weight already extracts a max; this post parks the leftover behind a cooldown queue. Top K Frequent counts, then heaps; this counts, then schedules.

The problem

Given a char[] tasks of uppercase letters and a non-negative int n, the same letter must be separated by at least n other slots — any other letter or idle. Return the minimum number of slots to finish every task.

tasks = [X, X, X, Y, Y, Z], n = 2  →  7
  // X Y Z X Y idle X

tasks = [P, P, Q], n = 1           →  3
  // P Q P

tasks = [K, L, M], n = 2           →  3
  // all unique; cooldown never binds

First row: three X, two Y, one Z. The X’s force the skeleton X _ _ X _ _ X. Fill Y and Z into the gaps; one idle remains. Second: one slot between the two P’s, Q fills it. Third: every letter is different, so the answer is just the length.

Note: n = 0 means no cooldown. The answer is tasks.length. The heap still works; it just never waits.

Rescan remaining counts each slot is the honest brute force

Count frequencies — int[26] is enough for A–Z. Then simulate time. Each slot, walk the 26 leftovers, pick an available type with the highest remaining count (ready time ≤ now), and run it. If none is free, idle. Track when each letter may run again: after a run at time t, the next same letter is legal at t + n + 1. Correct. Slow in the length of the timeline.

int leastIntervalScan(char[] tasks, int n) {
    int[] freq = new int[26];
    int[] readyAt = new int[26];
    for (char t : tasks) {
        freq[t - 'A']++;
    }
    int left = tasks.length;
    int time = 0;
    while (left > 0) {
        time++;
        int pick = -1;
        for (int i = 0; i < 26; i++) {
            if (freq[i] == 0 || readyAt[i] > time) {
                continue;
            }
            if (pick < 0 || freq[i] > freq[pick]) {
                pick = i;
            }
        }
        if (pick >= 0) {
            freq[pick]--;
            left--;
            readyAt[pick] = time + n + 1;
        }
    }
    return time;
}

At a dozen tasks this is a rounding error. At a long cooldown with one hot type you still walk 26 buckets every idle slot for a question a heap answers with one poll: which type has the most remaining right now?

Max-heap of remaining counts, queue until ready

Count once. Offer every positive count into a max-heap. PriorityQueue is a min-heap; pass Collections.reverseOrder() so the root is the loudest leftover. Say the invert out loud.

A cooldown queue holds [remainingCount, availableAt]. Use ArrayDeque, not Stack. After you run a type at time t and it still has leftovers, park remaining - 1 until t + n — increment t first, then run, so availableAt = t + n means the next same type is legal at t + n + 1.

  • Time starts at 0. While the heap or the cooldown queue is nonempty, increment time.
  • If the heap is nonempty, poll, run that type this slot, and park the leftover if any remain.
  • If the heap is empty, this slot is idle — only legal while cooldown is still pending.
  • Then release any type whose availableAt equals the current time back onto the heap.

You never rescan 26 buckets. You never busy-spin: empty heap still advances time.

tasks = [X, X, X, Y, Y, Z], n = 2
count: X→3  Y→2  Z→1
max-heap of remaining: 3, 2, 1

t=1  poll 3  left 2  park (2, ready=3)     heap 2, 1
t=2  poll 2  left 1  park (1, ready=4)     heap 1
t=3  poll 1  left 0  no park               heap empty
     ready=3: offer 2                      heap 2
t=4  poll 2  left 1  park (1, ready=6)     heap empty
     ready=4: offer 1                      heap 1
t=5  poll 1  left 0  no park               heap empty
t=6  heap empty → idle
     ready=6: offer 1                      heap 1
t=7  poll 1  left 0                        done
→ 7

The Java is that walk. Counts only — letter identity is gone after the frequency pass. n = 0 parks with availableAt = time, so the leftover returns the same iteration and the heap just drains:

int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char t : tasks) {
        freq[t - 'A']++;
    }
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    for (int f : freq) {
        if (f > 0) {
            heap.offer(f);
        }
    }
    Queue<int[]> cooldown = new ArrayDeque<>();
    int time = 0;
    while (!heap.isEmpty() || !cooldown.isEmpty()) {
        time++;
        if (!heap.isEmpty()) {
            int left = heap.poll() - 1;
            if (left > 0) {
                cooldown.offer(new int[] { left, time + n });
            }
        }
        if (!cooldown.isEmpty() && cooldown.peek()[1] == time) {
            heap.offer(cooldown.poll()[0]);
        }
    }
    return time;
}

Time is O(T log U) — T is the number of slots you return, U is the number of distinct letters (at most 26). Each slot does at most one poll and one cooldown release. Space is O(U) for the heap and the cooldown queue. Do not re-lecture sift at the whiteboard unless they ask.

Note: If the heap is empty and cooldown is not, you still increment time. Waiting in a loop without advancing the clock never unblocks a readyTime in the future. A natural-order PriorityQueue polls the rarest type first and leaves the hot type’s gaps unfilled — a legal-looking schedule that is not the shortest.

What interviewers usually poke next

  • n = 0. No cooldown. Return tasks.length. The heap drains in one pass; time + n equals the current slot, so leftovers re-enter immediately.
  • All unique tasks. Cooldown never binds. Answer is again tasks.length, even when n is large.
  • Idle-gap formula. (maxFreq - 1) * (n + 1) + countOfMax, then max(that, tasks.length). The first term is the skeleton the hottest types force; the max with length covers the packed case where other letters fill every gap and then some. Idle-heavy vs packed. Heap simulation is the default when they said heap. The formula is the follow-up.
  • Why most-frequent-first. The hottest type writes the skeleton. Other letters fill the gaps. Burn the rare types first and those gaps have nothing left to sit in, so you idle more.
  • Jump the idle. When the heap is empty you may set time = cooldown.peek()[1] instead of ticking one-by-one. Then release with <= time, and the returned time must still count those skipped slots. Easy to drop idle from the answer. The tick-by-tick loop is safer on the board.
  • Later sibling: Reorganize String. Same greedy heap, cooldown of 1, except the string cannot idle — if two of the same letter would sit together, return empty. Do not solve it here.

You are done with this problem when you can say, out loud, why rescanning leftovers each slot is correct, why a reversed PriorityQueue plus an ArrayDeque cooldown peeks the next-ready loudest type, and why the idle-gap formula is the follow-up rather than the heap they asked for.