Find the least time to run tasks when identical tasks need n idle slots between them, using the max-frequency formula in O(m). A popular greedy FAANG question.
The problem
tasks is a list of task letters; each takes one unit of time. Two identical tasks must be at least n units apart (the CPU may idle). Return the minimum total time.
Examples
Example 1
Input
least_interval(['A', 'A', 'A', 'B', 'B', 'B'], 2)
Expected output
8
Example 2
Input
least_interval(['A', 'A', 'A', 'B', 'B', 'B'], 0)
Expected output
6
+ 3 hidden tests on Submit — no idling needed.
Edge cases to ask about
- n = 0
- Several tasks tied for most frequent
- No idling needed
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Simulate with a max-heap and a cooldown queue | O(T · log k) | O(k) | T = total time steps. |
| bestFrame formula from the most frequent task | O(m) | O(k) | (top − 1) frames of size n + 1, plus the tied tasks at the end. |
Walkthrough of the optimal approach (try it yourself first)
The most frequent task (count top) forces top − 1 full frames of length n + 1, followed by one last slot for each task tied at top. Other tasks fill the idle gaps. If they more than fill them, no idling is needed and the answer is simply len(tasks) — hence the max.
Simulating with a max-heap and a cooldown queue is the general method; the formula is the elegant answer interviewers hope for.
Complexity: O(m) time, O(1) space. Counting the m tasks is linear; the alphabet of task types is fixed (26 letters), so the counter is O(1).
Reveal the reference solution
from collections import Counter def least_interval(tasks, n): counts = Counter(tasks) if not counts: return 0 top = max(counts.values()) tied = sum(1 for c in counts.values() if c == top) return max(len(tasks), (top - 1) * (n + 1) + tied)
Follow-ups interviewers ask
- Output an actual schedule.
- Tasks must run in the given order (no reordering).
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Task Scheduler With Cooldown in Python?
The optimal solution runs in O(m) time and O(1) auxiliary space. Counting the m tasks is linear; the alphabet of task types is fixed (26 letters), so the counter is O(1).
What is the brute-force approach, and how do you optimise it?
Simulate with a max-heap and a cooldown queue: O(T · log k) time, O(k) space. T = total time steps. Frame formula from the most frequent task: O(m) time, O(k) space. (top − 1) frames of size n + 1, plus the tied tasks at the end.
What follow-up questions do interviewers ask about Task Scheduler With Cooldown?
Output an actual schedule. Tasks must run in the given order (no reordering).