Task Scheduler
Understanding the Problem
We have a set of CPU tasks and a cooldown constraint. After executing a task of type X, we must wait at least n intervals before executing another task of type X. During the wait, we can either execute a different task or sit idle.
The question is: what is the minimum total number of intervals (task executions + idle slots) needed to complete every task?
The task that appears most frequently is the bottleneck. If task A appears 6 times and n = 2, then we need at least 5 gaps of size (n+1) between consecutive A executions, plus the final A itself. Other tasks can fill those gaps and reduce idle time, but they cannot reduce the minimum imposed by the most frequent task.
The problem reduces to two questions: how many idle slots does the most frequent task force, and how many of those slots can other tasks fill?
Key Constraints:
1 <= tasks.length <= 10^4→ An O(n log n) or O(n * 26) approach runs comfortably within limits.tasks[i]is an uppercase English letter → At most 26 distinct task types, so sorting or scanning the 26 frequencies is effectively O(1).0 <= n <= 100→ When n = 0, the answer is the number of tasks. With few distinct tasks and a large cooldown, idle slots become common.
Approach 1: Simulation with Max-Heap
Intuition
Simulate the CPU step by step. At each time step, execute the available task with the highest remaining count. Delaying high-frequency tasks increases the chance of forced idle time later, because they need more gaps to spread out, so executing them as early as possible is the greedy choice.
A max-heap gives the most frequent available task in O(log 26) per step. The complication is cooldown: after a task executes, it cannot run again for the next n intervals, so it must leave the heap temporarily and return once its cooldown expires. A queue holds the cooling tasks, each paired with the time it becomes available.
At each time step, pop the most frequent task from the heap, decrement its count, and push it into the cooldown queue with availability time current + n + 1. Before popping, check whether the task at the front of the queue has become available, and if so move it back to the heap. If the heap is empty, the step is an idle interval.
Algorithm
- Count the frequency of each task
- Push all frequencies into a max-heap
- Initialize a time counter and a cooldown queue
- While the heap or queue is non-empty:
- Increment time
- If the front of the cooldown queue has an availability time equal to the current time, move that frequency back to the heap
- If the heap is non-empty, pop the highest frequency, decrement it, and if it is still positive, add it to the cooldown queue with availability time = current time + n + 1
- If the heap is empty (and we didn't move anything from the queue), this is an idle interval
- Return time
Example Walkthrough
Code
- Time Complexity: O(T * log 26) where T is the total number of intervals. At each time step, we do at most one heap push and one heap pop on a heap of at most 26 elements. T can be much larger than tasks.length when there are many idle slots.
- Space Complexity: O(1). The heap and cooldown queue each hold at most 26 entries, and the frequency array is size 26.
This simulation processes one time step at a time, including every idle slot. The next approach processes a full round of n + 1 slots per iteration instead.
Approach 2: Greedy with Sorting (Round-Robin)
Intuition
Group the schedule into rounds of at most (n + 1) slots. A round is the smallest window in which any task can repeat: after executing a task, the next (n + 1) slots are exactly the cooldown window plus the slot the task occupied. Within one round, each distinct task can appear at most once, so filling a round with the (n + 1) most frequent remaining tasks never violates the constraint. When fewer than (n + 1) distinct tasks remain, the leftover slots are idle.
This maps to a table with (n + 1) columns, where each row is a round filled left to right from most frequent to least frequent. The number of rows equals the frequency of the most common task, since that task occupies one slot in every round until it runs out. The last row may be shorter because some tasks have been fully consumed.
Re-sorting after each round keeps the highest remaining frequencies at the end of the array. The work per round is O(1) because the array has fixed size 26.
Algorithm
- Count frequencies of each task
- Sort frequencies in ascending order (so the highest is at index 25)
- While the most frequent task still has remaining executions:
- Process one round of at most (n + 1) tasks, picking from most frequent to least
- Decrement each picked task's frequency
- Add the number of slots used (tasks + idle) to the time counter
- Re-sort the frequencies
- Return total time
Example Walkthrough
Code
- Time Complexity: O(maxFreq * 26 log 26), which simplifies to O(maxFreq). We run at most maxFreq rounds, and in each round we re-sort a 26-element array, which is O(1).
- Space Complexity: O(1). We only use the frequency array of fixed size 26.
Both previous approaches loop through the schedule. The frequency distribution alone determines the answer, so the next approach computes it with a closed-form formula and no loop over rounds.
Approach 3: Math Formula (Optimal)
Intuition
Instead of simulating the schedule, derive the answer directly from the frequencies.
Consider the task with the highest frequency, maxFreq. It runs maxFreq times, and each consecutive pair of executions needs at least n intervals of cooldown between them. The most frequent task alone creates (maxFreq - 1) blocks, each of size (n + 1), followed by a final partial block.
If A appears 3 times and n = 2:
A _ _ | A _ _ | A
That is 2 blocks of 3 slots each, plus a final A. But what if multiple tasks share the maximum frequency? If both A and B appear 3 times:
A B _ | A B _ | A B
The final block now has 2 tasks instead of 1. If maxCount is the number of tasks with frequency equal to maxFreq, the formula becomes: result = (maxFreq - 1) * (n + 1) + maxCount.
There is one more case. When there are many distinct tasks and a small cooldown, the tasks themselves fill more than the formula predicts. So the final answer is: max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount).
The formula takes the maximum of two lower bounds. The first bound, (maxFreq - 1) * (n + 1) + maxCount, is forced by the most frequent task: its (maxFreq - 1) cooldown gaps cannot be compressed, and the final block must hold every task that ties at maxFreq. The second bound, tasks.length, holds because each task occupies one interval and idle slots only add to that count.
The maximum of these bounds is also achievable, which is what makes it exact. When idle slots exist (few distinct tasks), spreading the most frequent tasks evenly across blocks and filling the gaps with less frequent ones leaves exactly the idle slots the first bound counts. When there are enough distinct tasks to fill every gap, no block is ever short, so no idle time is needed and the schedule length equals tasks.length.
Algorithm
- Count the frequency of each task
- Find
maxFreq, the highest frequency among all tasks - Count
maxCount, how many tasks have frequency equal tomaxFreq - Compute
formulaResult = (maxFreq - 1) * (n + 1) + maxCount - Return
max(tasks.length, formulaResult)
Example Walkthrough
Code
- Time Complexity: O(n) where n is the number of tasks. We iterate through tasks once to count frequencies, then iterate through the 26-element frequency array twice. Everything is O(n + 26) = O(n).
- Space Complexity: O(1). The frequency array has a fixed size of 26, regardless of input size.