Task Scheduler
Problem Statement
You are given an array of CPU tasks represented by uppercase letters and a non-negative cooldown n. Each interval can run one task or stay idle. The same task type must be separated by at least n intervals. Return the least number of intervals needed to finish all tasks.
Input
A character array tasks and an integer cooldown n.
Output
An integer: the minimum total number of CPU intervals, including idle intervals if they are unavoidable.
Constraints
- •
1 <= tasks.length <= 10^4 - •
tasks[i] is an uppercase English letter - •
0 <= n <= 100
Examples
Example 1
tasks = [A,A,A,B,B,B], n = 2
8Example 2
tasks = [A,C,A,B,D,B], n = 1
6Learning Objectives
- Recognise cooldown scheduling as a most-frequent-task-first greedy problem.
- Use a max-heap of remaining counts to choose the task type with the largest backlog.
- Explain why tasks used in the same cooldown cycle are requeued only after the cycle ends.
- Compare the heap simulation with the constant-space counting formula.
Intuition
Pattern Recognition
The signal is cooldown, least intervals, and repeated task types. The hardest task type is the one with the most remaining copies, because it creates the most separation requirements. A max-heap lets us repeatedly pick the task type with the largest remaining count.
Think in cycles of length n + 1. Within one cycle, we can run at most one copy of the same task type. So we pop up to n + 1 largest counts, run each once, decrement them, and hold them aside until the cycle ends. If work remains but fewer than n + 1 distinct tasks were available, the empty positions in that cycle are forced idle intervals.
Common mistakes
- ×Reinserting a task into the heap immediately after running it, which violates cooldown inside the same cycle.
- ×Adding idle time after the final cycle even though all tasks are already complete.
- ×Using alphabetical order instead of remaining frequency as the priority.
- ×Forgetting that when **n = 0**, the answer is simply the number of tasks.
Algorithm Explanation
Key idea
Count task frequencies and put the positive counts in a max-heap. The root is the task type with the largest backlog. Process one cooldown cycle at a time, where each cycle has length n + 1. Pop up to n + 1 counts, decrement each because one task ran, then requeue only the counts that remain positive after the cycle.
Heap walkthrough
Use tasks = [A,A,A,B,B,B] and n = 2. The heap starts as [3,3], representing three A tasks and three B tasks. Cycle one has three slots: run A, run B, then idle because no third distinct task is available; requeue counts [2,2] and time becomes 3. Cycle two repeats: run A, run B, idle, then requeue [1,1] and time becomes 6. Cycle three runs A and B with no idle afterward because the heap becomes empty. Total time is 8.
Algorithm
- Count how many times each task type appears.
- Push every positive count into a max-heap.
- While the heap is not empty, start a cycle of length n + 1.
- Pop up to n + 1 counts, run each task once, and store decremented positive counts in a temporary list.
- Requeue all temporary counts after the cycle choices are made.
- If the heap still has work, add the full cycle length to time; otherwise add only the number of tasks actually run in the final cycle.
- Return the accumulated time.
Solutions
Solution: Max-heap cooldown simulation
Use this when you want an interview-friendly simulation that directly explains cooldown cycles before mentioning the formula.
Use a max-heap of remaining task counts. In each cycle of length n + 1, run the most frequent available task types once, hold their decremented counts aside, then requeue them after the cycle.
Step-by-step
- Count frequencies for all task letters.
- Push every positive count into a max-heap.
- While work remains, create an empty temporary list and run up to n + 1 tasks from the heap.
- Decrement each popped count and keep it in the temporary list if it is still positive.
- Reinsert the temporary counts only after the cycle finishes.
- Add a full cycle to time if more work remains, otherwise add only the tasks run in the final partial cycle.
O(m log u)
O(u)
Here **m** is the number of tasks and **u** is the number of distinct task types. For uppercase English letters, **u <= 26**, so this is effectively O(m) time and O(1) extra space.
Java implementation
Dry Run
Sample input
tasks = [A,A,A,B,B,B], n = 2. Heap entries are remaining counts, not task letters.
| cycle | heap before | tasks run | idle slots | time after |
|---|---|---|---|---|
| 1 | [3,3] | A and B | 1 | 3 |
| 2 | [2,2] | A and B | 1 | 6 |
| 3 | [1,1] | A and B | 0 | 8 |
The first two cycles need one idle slot because only two task types are available for three cooldown positions. The final cycle does not add trailing idle time.
Interview Tips
Lead with the heap simulation because it is easy to reason about and less error-prone than memorising a formula. Then mention the O(1) counting formula: max(tasks.length, (maxFreq - 1) * (n + 1) + tiedMaxFreq), where tiedMaxFreq is the number of task types that share the maximum frequency. The formula counts the frame forced by the most frequent tasks.
Likely follow-ups
- Can you derive the O(1) counting formula from the most frequent task type?
- How would the solution change if task types were arbitrary strings instead of uppercase letters?
- How would you output one actual optimal schedule, not just its length?
- What if every task type had a different cooldown?
Similar Problems
Key Takeaways
- The most frequent remaining task type creates the tightest cooldown constraint.
- A cooldown cycle has length **n + 1** and can contain each task type at most once.
- Tasks run in a cycle are requeued only after that cycle finishes.
- Do not add idle intervals after all work is complete.