Task Scheduler
Problem Statement
You are given an array tasks of uppercase letters and an integer n. Each CPU interval can execute one task or stay idle. Identical tasks 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 a non-negative cooldown n.
Output
An integer: the minimum CPU intervals needed, 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,A,A,B,B,B], n = 0
6Example 3
tasks = [A,A,A,A,B,B,C,C], n = 2
10Learning Objectives
- Derive the idle-slot formula from the most frequent task count.
- Explain why the most frequent tasks determine the minimum schedule length.
- Handle ties among maximum-frequency tasks correctly.
- Compare the formula approach with a max-heap simulation.
Intuition
Greedy Insight: The rare tasks are flexible; the most frequent tasks are the constraint. If task A appears the most, its copies must be spread out with at least n intervals between them. Those copies create a skeleton of cooling gaps that other tasks can fill.
If several tasks tie for maximum frequency, they occupy the same final layer of the skeleton. That is why the formula adds the number of maximum-frequency tasks at the end.
The wrong sort key trap is to schedule tasks alphabetically or by original order. The optimal structure is driven by frequency, not by labels. A heap simulation follows the same greedy idea by repeatedly choosing the currently most frequent available tasks, while the formula jumps straight to the length forced by the highest frequency.
Common mistakes
- ×Forgetting to count how many task types share the maximum frequency.
- ×Returning the frame length even when there are enough other tasks to fill every idle slot, where the answer should be **tasks.length**.
- ×Using **maxFrequency * (n + 1)** instead of **(maxFrequency - 1) * (n + 1)** for the repeated gaps.
- ×Treating cooldown as a delay after the final copy of a task, which is unnecessary.
Algorithm Explanation
Greedy strategy Count task frequencies. Let maxFrequency be the largest count and maxFrequencyTasks be how many task types have that count. Build the shortest frame forced by those most frequent tasks, then take the larger of the frame length and the total number of tasks.
Why it works The most frequent tasks create maxFrequency - 1 full gaps before their final occurrence. Each full gap must have length n + 1 when including the anchor task at its start. The last block contains all task types tied at the maximum frequency. Other tasks can only fill idle slots inside this skeleton; they cannot reduce the skeleton itself.
Proof of correctness Any valid schedule must place the maxFrequency copies of a most frequent task with at least n intervals between consecutive copies. Therefore the schedule length is at least (maxFrequency - 1) * (n + 1) + 1 for one such task, and if maxFrequencyTasks tasks tie for that count, their final copies require maxFrequencyTasks positions in the last block. This gives the lower bound (maxFrequency - 1) * (n + 1) + maxFrequencyTasks.
Now take a schedule built from that frame and fill its idle slots with all remaining tasks greedily. If remaining tasks fit, the frame length is achievable. If they do not fit, then there are enough tasks to occupy every idle position and extend the schedule with no idle time, so tasks.length is achievable and is also a lower bound because every task must run once. Thus max(tasks.length, frameLength) is both necessary and sufficient.
As an exchange argument, if a schedule leaves a frame anchor for a less frequent task while a maximum-frequency task is still waiting, swap the maximum-frequency task into that anchor. The swap cannot create more cooldown pressure than before because maximum-frequency tasks are the only ones that define the widest required spacing.
Algorithm
- Count frequencies for the 26 uppercase letters.
- Find maxFrequency.
- Count how many letters have that frequency.
- Compute frameLength = (maxFrequency - 1) * (n + 1) + maxFrequencyTasks.
- Return max(tasks.length, frameLength).
Solutions
Solution 1: Idle-slot frequency formula
The formula computes the shortest schedule forced by the most frequent task types. All other tasks are filler; they either occupy idle slots or, if there are enough of them, make the answer simply the number of tasks.
Step-by-step
- Count how often each uppercase task appears.
- Track the largest frequency.
- Count task types whose frequency equals that maximum.
- Compute the forced frame length using the most frequent tasks.
- Return the larger of total tasks and forced frame length.
O(m + 26)
O(26)
Here **m** is tasks.length; the alphabet size is fixed.
Java implementation
Solution 2: Max-heap cycle simulation
Use this when an interviewer asks for the actual scheduling process or wants to see the greedy choice operationally. The formula is shorter, but the heap makes cooldown cycles explicit.
Store remaining task counts in a max-heap. In each cycle of length n + 1, run up to that many distinct task types, decrement their counts, and push unfinished tasks back after the cycle.
Step-by-step
- Count each task frequency and push positive counts into a max-heap.
- Repeatedly open a cycle of length n + 1.
- Pop and execute the largest remaining counts, storing any unfinished counts temporarily.
- Push unfinished counts back after the cycle so the same task is not reused inside its cooldown window.
- Add either the full cycle length or the number of used slots if the heap is empty.
O(answer log 26)
O(26 + n)
The heap has at most 26 task types; **answer** includes idle intervals produced by the simulation.
Java implementation
Dry Run
Sample input
tasks = [A,A,A,B,B,B], n = 2. Frequencies are A = 3 and B = 3.
| calculation | value | reason | running answer |
|---|---|---|---|
| frequencies | A = 3, B = 3 | two task types tie for most frequent | unknown |
| maxFrequency | 3 | three copies create two full cooldown gaps | unknown |
| maxFrequencyTasks | 2 | A and B both occupy the final block | unknown |
| frameLength | 8 | (3 - 1) * (2 + 1) + 2 | 8 |
| tasks.length | 6 | six real tasks leave two unavoidable idle slots | max(6, 8) = 8 |
The forced frame has length 8, matching the schedule A, B, idle, A, B, idle, A, B. Since the total task count is only 6, the two idle intervals cannot be eliminated.
Interview Tips
Present the formula as a lower-bound argument, not as a memorised trick. Say that the most frequent tasks create the skeleton, ties widen the last block, and other tasks merely fill gaps. If asked to construct a schedule, switch to the max-heap cycle simulation and explain that it chooses the currently most frequent available tasks first.
Likely follow-ups
- How would you output one valid shortest schedule, not just its length?
- What changes if each task type has a different cooldown?
- How would the solution change with multiple identical CPUs?
- Can you derive the same answer using a priority queue simulation?
Similar Problems
Key Takeaways
- The most frequent task type determines the cooldown skeleton.
- Ties among maximum-frequency tasks add width to the final block.
- The answer is the larger of the forced frame length and the number of tasks.
- A max-heap simulation is useful for construction, but the formula is the expected optimal solution.