Coding · Greedy
Task Scheduler
- Reported once
- Medium
- SDE-1
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
A processor runs one task per time slot or sits idle, and each task is a capital letter that may run in any order. Two runs of the same letter must have at least n other slots (tasks or idle) between them, and you return the fewest slots needed to finish all tasks. For example, tasks ["A","A","A","B","B","B"] with n = 2 need 8 slots: A B idle A B idle A B. There are up to 10,000 tasks.
Restated in our own words, not a quote from Swiggy or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: may different letters run back to back with no gap? Can I reorder the tasks freely? Do I return only the number of slots, not the schedule itself? Is n zero allowed, meaning no cooldown at all? How many tasks, and are the labels limited to the 26 capital letters?
I will assume different letters have no restriction on each other, order is free, I return only the length, n can be 0, and the labels are capital letters. An empty task list needs 0 slots. I will state that I may also describe a schedule-building version afterwards.
Brute force
Say the obvious answer and why it is too slow.
The honest brute force is a search over schedules: at each slot, try running each task that is allowed or sitting idle, and keep the shortest complete schedule. That explores a number of orderings that grows like a factorial in the number of tasks, so it breaks down beyond about a dozen tasks, nowhere near 10,000.
A second, polynomial idea is to simulate the clock with a max-heap: each slot, run the available letter with the most copies left, and park it in a cooldown queue for n slots. That is correct and costs about O(S log 26) for S slots, where S can be much larger than the number of tasks when n is big. But it builds a whole schedule just to report its length, and it has several moving parts to get right under pressure. Counting alone gives the same number.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(T!)
- Time
- O(T)
- Space
- O(1) extra
The letter that appears most often is the bottleneck. Say its count is f. Its copies need gaps, so picture the schedule as f - 1 full frames, each of width n + 1 (the letter, then n slots for cooldown), followed by a last row. Every other letter can be dropped into the spare slots of the frames.
The last row is not just the busiest letter: any other letter that also appears exactly f times needs its final copy somewhere too, and the only place without breaking its own cooldown is that last row. If tied letters share the maximum count, the last row holds tied tasks. So the schedule is at least (f - 1) * (n + 1) + tied slots long.
That formula is a lower bound, because the busiest letters alone force it. The other bound is simply the number of tasks, since each slot runs at most one. When there are so many tasks that the frames overflow, the extra tasks can be spread through the schedule and no idle slot is needed. So the answer is the larger of the two: max(tasks.length, (f - 1) * (n + 1) + tied).
I would say this out loud as: "the most common letter decides the frame; idle time only appears when the other tasks cannot fill it." If asked for a rigorous proof, I would point to the heap simulation, which builds a matching schedule. The pattern is greedy counting.
Walk it through
A dry run on the example, step by step.
| step | quantity | value | meaning |
|---|---|---|---|
| 1 | counts | A=3, B=3 | frequency table |
| 2 | f (max count) | 3 | busiest letter's runs |
| 3 | tied | 2 | letters with count f |
| 4 | full frames | f - 1 = 2 | frames before last row |
| 5 | frame width | n + 1 = 3 | one run plus cooldown |
| 6 | frame slots | 2 x 3 = 6 | slots in full frames |
| 7 | last row | tied = 2 | A and B end the plan |
| 8 | frame bound | 6 + 2 = 8 | forced by busiest |
| 9 | task count | 6 | needed even with no idle |
| 10 | answer | max(8, 6) = 8 | larger bound wins |
Take tasks A A A B B B with n = 2. Counting gives A: 3 and B: 3, so the highest count f is 3, and two letters share it, so tied is 2.
There are f - 1 = 2 full frames of width n + 1 = 3, which is 6 slots. The last row holds the two tied letters, adding 2, for 8 slots. The number of tasks is only 6, so the frame bound wins: the answer is max(8, 6) = 8, matching A B idle A B idle A B.
The trace table lists each quantity in order, from the counts to the final maximum.
The code
Runnable JavaScript, checked against test cases.
function leastInterval(tasks, n) {
const counts = new Map();
for (const task of tasks) {
counts.set(task, (counts.get(task) || 0) + 1);
}
let maxFrequency = 0;
for (const count of counts.values()) {
maxFrequency = Math.max(maxFrequency, count);
}
let tiedForMax = 0;
for (const count of counts.values()) {
if (count === maxFrequency) tiedForMax++;
}
const framedLength = (maxFrequency - 1) * (n + 1) + tiedForMax;
return Math.max(tasks.length, framedLength);
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
If n is 0, the frame width is 1 and the formula gives at most the number of tasks, so the answer is the task count and no idle appears. An empty list gives a highest count of 0, a negative frame total, and the maximum with the task count of 0 returns 0.
Many distinct letters with a small n, for example A, B, C with n = 5 once each, has a highest count of 1 with three letters tied, so the frame bound is 0 * 6 + 3 = 3, which equals the task count: no idle is needed. A single repeated letter, such as six copies of A with n = 2, gives (6 - 1) * 3 + 1 = 16, with lots of idle time. Several letters tying for the maximum are handled by the tied count.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the actual schedule, and why does a max-heap with a cooldown queue work?
- What if the cooldown depends on the letter?
- How would you spread the tasks over k identical processors?
- Can you prove that the max of the two bounds is always achievable?
Where candidates slip
The mistakes this problem punishes.
The commonest slip is forgetting the tied count and using (f - 1) * (n + 1) + 1, which is wrong when two letters share the highest count: A A A B B B with n = 2 would give 7 instead of 8. A second is using f * (n + 1), which counts idle slots in the last row that are not needed.
Other slips: omitting the maximum with the task count, so inputs with many distinct letters return an answer smaller than the number of tasks, which is impossible; mixing up n and n + 1; counting distinct letters instead of letters tied at the top count; and writing a heap simulation that decrements the cooldown at the wrong moment, so that the gap between two copies is one slot too short or too long.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.