Task Scheduler
Problem statement
You're given a list of CPU tasks, each labeled with a letter (A through Z), and a cooldown number n. Each time unit either runs one task or sits idle. The rule: the same letter can't run again until at least n other time units — running a task or idling, either counts — have passed since it last ran.
Tasks can run in any order you choose. Find the fewest total time units needed to get every task done at least once.
Examples
Example 1
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: one valid order is A → B → idle → A → B → idle → A → B. After each A or B, two other slots have to pass before that same letter can run again, which forces two idle slots.
Example 2
Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: with only a 1-slot cooldown, there are enough other distinct tasks (C and D) to fill every gap, so A → B → C → D → A → B finishes with no idle time at all — the same as just running all 6 tasks back to back.
Example 3
Input: tasks = ["A","A","A","B","B","B"], n = 3
Output: 10
Explanation: with only two distinct letters but a 3-slot cooldown, there aren't enough other tasks to fill every gap, so two idle slots are forced in each round: A → B → idle → idle → A → B → idle → idle → A → B.
Hints
Approach
Optimal: Math formula from the most frequent task
Intuition
Neither simulation is actually necessary. The letter with the highest count, maxFreq, is the one that decides the shape of the whole schedule: picture laying out its copies with n empty slots after each one, like A _ _ A _ _ A. That's maxFreq - 1 gaps, each needing n slots to be filled — by other tasks if there are enough of them, or by forced idle time if there aren't. If more than one letter shares that same maximum count, each of those extra letters needs one more slot tacked onto the very end, since they can't fit into an existing gap for free.
That gives a formula: (maxFreq - 1) * (n + 1) + numAtMax, where numAtMax is how many letters tie for the highest count. But if there are enough distinct tasks to fill every gap completely with no idle time left over, that formula can come out smaller than just the total number of tasks — in that case there's no way to finish any faster than running every task once, so the true answer is whichever of the two is bigger.
Steps
- Count how many times each letter appears (an array of 26 counts is enough, since there are only 26 possible letters).
- Find
maxFreq, the highest count among all letters. - Count
numAtMax, how many letters share that highest count. - Compute
(maxFreq - 1) * (n + 1) + numAtMax— the schedule length forced by the busiest letter(s) and their gaps. - Return whichever is larger: that computed value, or the total number of tasks.
Dry run
tasks = ["A","A","A","B","B","B"], n = 2. Counts: A = 3, B = 3.
maxFreq = 3 (both A and B reach it). numAtMax = 2 (A and B both tie for the maximum).
Formula: (3 - 1) * (2 + 1) + 2 = 2 * 3 + 2 = 8. Total task count is 6. The answer is max(6, 8) = 8, matching every other approach.
For contrast, tasks = ["A","C","A","B","D","B"], n = 1: counts are A = 2, B = 2, C = 1, D = 1, so maxFreq = 2, numAtMax = 2. Formula: (2 - 1) * (1 + 1) + 2 = 4. But there are 6 tasks total, and max(6, 4) = 6 — here the raw task count wins, because C and D are enough to fill every gap with no idle time to spare.
Edge cases: when every task has the same single letter (maxFreq equals the total task count, numAtMax = 1), the formula reduces to (count - 1) * (n + 1) + 1, which correctly accounts for the full cooldown after every single occurrence.
Complexity
Time O(m) - one pass over the tasks to count each letter, then one pass over at most 26 counts to find the maximum and how many letters share it.
Space O(1) - a fixed array of 26 counts, regardless of how many tasks there are.
from collections import Counter
class Solution:
def leastInterval(self, tasks: list[str], n: int) -> int:
counts = Counter(tasks)
maxFreq = max(counts.values())
numAtMax = sum(1 for c in counts.values() if c == maxFreq)
framedTime = (maxFreq - 1) * (n + 1) + numAtMax
return max(len(tasks), framedTime)
if __name__ == "__main__":
print(Solution().leastInterval(["A","A","A","B","B","B"], 2)) # 8
print(Solution().leastInterval(["A","C","A","B","D","B"], 1)) # 6
print(Solution().leastInterval(["A","A","A","B","B","B"], 3)) # 10RecapThe whole problem in a few lines, for the night before
- Spot it: "schedule tasks with a cooldown between repeats of the same task, minimize total time" — the busiest task drives the schedule
- Idea:
(maxFreq - 1) * (n + 1) + numAtMax, then take the max with the total task count, since enough other tasks can fill every gap with no idle time - Cost: O(m) time, O(1) space — only 26 possible letters
- Trap: forgetting
numAtMaxwhen several letters tie for the highest frequency — using1instead undercounts the trailing row of the schedule
Interview follow-ups
What if you need the actual schedule, not just its length — for example to print or log it?
The max-heap approach already produces one, letter by letter, so use that instead of the math formula. Each time a letter is popped and run, record it (or record "idle" when the heap is empty that tick); at the end, the recorded sequence is a valid schedule of the same minimum length the formula predicts.
The cooldown
ncan now be different for each task letter instead of one shared value. Does the approach still work?The math formula breaks, since it assumes one shared cooldown drives the gap size for every letter. The max-heap simulation adapts more easily: track each letter's own cooldown length, and when pushing a letter into the cooldown queue, tag it with
time + n[letter]instead of a single sharedn. The rest of the simulation logic is unchanged.
Frequently asked questions
Because the gaps left by the busiest task are the tightest constraint in the whole schedule. Every other task, however frequent, only needs to worry about not colliding with itself — and there's always at least as much room for that as there is for the busiest task, since nothing is busier. The formula only ever needs maxFreq and how many letters tie for it; every other count only matters insofar as it helps decide whether len(tasks) ends up being the bigger number.
Because the formula only accounts for the idle time forced by the busiest letter's gaps — it doesn't know whether other tasks exist to fill those gaps, or how many. When there are enough distinct, moderately-frequent tasks to fill every single gap, no idle time is needed at all, and the real answer is just "run every task once," which can be bigger than what the gap formula alone predicts. Taking the max of the two values covers both cases correctly.
Just the length — the problem only asks for the minimum number of time units, not the sequence itself. That's exactly why the Optimal approach can skip simulating anything: it reasons about the shape of an optimal schedule mathematically rather than building one.
Almost exactly as stated: scheduling a fixed set of recurring jobs (backups, health checks, log rotations) onto a shared worker or CPU, where the same job type can't run again until some cooldown has passed — rate limiting, throttling a noisy job, or spacing out retries against the same downstream service are all the same "space out the busiest repeat offender" shape.
