Task Scheduler
Schedule tasks with a cooldown period between same tasks. Greedily pick the most frequent available task. If no task is available, idle. Max-heap of frequencies + a queue with cooldown timestamps.
How It Works
Task Scheduler minimizes total time to run tasks when identical tasks must be separated by a cooldown of n slots. The simulation pairs a max-heap of remaining counts with a cooldown queue: each tick, pop the most frequent available task and execute it, then place it in the queue stamped with the time it becomes available again; if the heap is empty, the CPU idles. When the queue's front timestamp matches the current tick, that task rejoins the heap. Greedily running the highest-count task first spreads the tightest constraint across the timeline, minimizing forced idles.
A closed-form shortcut often replaces the simulation: with f_max the highest frequency and c the number of tasks sharing it, the answer is max(total_tasks, (f_max − 1) × (n + 1) + c). The frame count (f_max − 1) with n+1 slots per frame accounts for mandatory gaps; when other tasks fill all gaps, the total task count dominates.
Step-by-Step Visualization
Code
static int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char t : tasks) freq[t - 'A']++;
int maxFreq = 0;
for (int f : freq) maxFreq = Math.max(maxFreq, f);
int maxCount = 0;
for (int f : freq) if (f == maxFreq) maxCount++;
return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
}
// leastInterval(new char[]{'A','A','A','B','B','B'}, 2) → 8Tips & Gotchas
Practice Problems
- 1Task Scheduler
- 2Reorganize String
- 3Rearrange String k Distance Apart
- 4Maximum Number of Weeks for Which You Can Work
About the Reorganize / Schedule Pattern
Use a max-heap to always process the most frequent item first. After processing, apply a cooldown before it can be used again. This greedy approach minimizes idle gaps or spreads characters apart.
Need the K largest? Use a min-heap of size K — anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.
Common Heap Interview Problems
- Kth Largest Element
- Top K Frequent Elements
- Find Median from Data Stream
- Merge K Sorted Lists
- Task Scheduler
- K Closest Points to Origin
Frequently Asked Questions
Should I present the formula or the heap simulation in an interview?
Lead with the formula for the classic version — it is O(number of task types) and shows insight into the frame structure — but know the heap simulation, since variants like returning the actual order, per-task cooldowns, or tasks arriving over time break the formula and require simulation.
What does the (f_max − 1) × (n + 1) + c formula actually count?
Picture the most frequent task pinned at the start of f_max frames, each frame n+1 slots wide so the cooldown is respected; the last frame holds only the c tasks tied at maximum frequency. Less frequent tasks pour into the remaining gap slots. If the tasks overflow the gaps, no idles are needed and the total is simply the task count — hence the outer max.
Why does the greedy 'most frequent first' rule minimize idle time?
Idle slots appear only when every remaining task type is cooling down, which happens when one task's copies outnumber the gaps the others can fill. Consuming the highest count earliest maximizes the distinct types available in later windows, deferring and often eliminating those forced idles.