Task Scheduler
Task Scheduler is LeetCode 621 (Medium). A CPU has to run a list of tasks, each an uppercase letter A to Z, with a cooldown n between equal tasks.
- In each interval the CPU runs exactly one task or stays idle.
- Two runs of the same letter must be separated by at least
nintervals. - Tasks may run in any order; different letters have no cooldown between them.
Return the minimum number of intervals needed to finish every task. There are up to 10⁴ tasks and n is at most 100, so the answer should come from the counts, not from simulating every order.
- 1 <= tasks.length <= 10⁴
- tasks[i] is an uppercase English letter.
- 0 <= n <= 100
Intuition
The order of the input does not matter, only how many times each task appears, and one task forces the shape of every schedule: the most frequent one. Its copies must sit n slots apart, so they mark out a frame of cooldown windows that no schedule can be shorter than.
Every other task has at most as many copies as that top task, so it can be spread one per window into the gaps without breaking its own cooldown. Gaps nobody fills become idle. If there are more tasks than gaps, the windows simply grow and no idle is needed. So the answer is the frame size or the task count, whichever is larger.
Scheduling with a minimum gap between equal items, where the order is yours to choose, is decided by the most frequent item. Reorganize String (767) is the LeetCode Task Scheduler picture with n = 1; Rearrange String k Distance Apart (358) needs the actual order, so it uses a max-heap and a cooldown queue.
Approach
Before reading on, draw a schedule for AAABBB with n = 2 using as few slots as you can. Count the idles, then try to explain the count from the frequencies alone.
Count the tasks
Build a frequency count. Let maxFreq be the highest count and numTop the number of tasks that have it. In the task scheduler Python code, Counter(tasks) builds the counts in one pass.
Size the frame
maxFreq − 1full rows ofn + 1slots: each row is one cooldown window, starting with a copy of a top task.- One last row holding only the
numToptop tasks. - Total:
frames = (maxFreq − 1) × (n + 1) + numTop.
Fill the frame with the other tasks
Place the remaining tasks column by column through the first maxFreq − 1 rows. A task with k ≤ maxFreq − 1 copies lands in k different rows, so its copies are always a full window apart. Empty slots that remain are the idle intervals.
Handle overflow
If the tasks do not fit in n + 1 columns, keep extending the rows. Gaps only grow, so the cooldown still holds and no idle is needed: the answer is len(tasks). Return max(len(tasks), frames).
Task Scheduler solution in Python | C++ | Java
+ numTop.+ numTop.Common pitfalls
Returning the frame count without the max
return (max_freq - 1) * (n + 1) + num_top
return max(len(tasks), (max_freq - 1) * (n + 1) + num_top)
With many distinct tasks the frame is too small. ["A","A","B","B","C","D"] with n = 1 gives a frame of 4, but 6 tasks need at least 6 intervals.
Adding 1 instead of numTop
frames = (max_freq - 1) * (n + 1) + 1
frames = (max_freq - 1) * (n + 1) + num_top
Every task tied for the highest count has a copy in the last row. AAABBB, n = 2 ends … A B, so the last row has 2 tasks and the answer is 8, not 7.
Using n instead of n + 1 as the row width
frames = (max_freq - 1) * n + num_top
frames = (max_freq - 1) * (n + 1) + num_top
A window holds the task itself plus n cooldown slots. With n as the width, two As end up only n − 1 apart.
Edge cases
No cooldown: the frame is maxFreq − 1 + numTop, never more than len(tasks), so the answer is len(tasks).
Complexity
len(tasks), read once to count. The count table has 26 entries at most, so extra space is constant.Greedy formula vs max-heap simulation
Both are accepted task scheduler solutions. The heap version is the one to reach for when the actual order is required, not just its length.
| Frame formula (this page) | Max-heap + cooldown queue | |
|---|---|---|
| Time | O(N) | O(N · log 26) plus one step per idle |
| Space | O(1) | O(26) |
| Gives the schedule itself | only by drawing the frame | yes, interval by interval |
| Idea | the most frequent task fixes the length | always run the most frequent available task |
| Generalises to | any "min gap between equal items" count | Rearrange String k Distance Apart (358) |
Task Scheduler FAQ
Is Task Scheduler the same as the job scheduler LeetCode problems?
No. Searches for a job scheduler on LeetCode usually mean one of two other problems. Maximum Profit in Job Scheduling (1235) picks non-overlapping jobs for the most profit, using sorting, DP and binary search. Minimum Difficulty of a Job Schedule (1335) splits jobs across days with DP. The task scheduler LeetCode problem, 621, has no profits or deadlines: only a cooldown, and the answer depends on the task counts alone.