Task Scheduler in a Coding Interview: The Idle-Slot Formula Explained
"Task Scheduler" is a favorite medium problem because it looks like a simulation but rewards a short counting argument. You get a list of tasks (letters) and a cooldown n: the same task must be separated by at least n other slots. Return the minimum number of time slots needed, idle slots included.
Start with the bottleneck
Only the most frequent task really matters. Say task A appears maxFreq times. Between consecutive A's you need n slots, so A alone forces a frame of (maxFreq - 1) blocks, each n + 1 long, plus a final row. If several tasks tie at maxFreq (call that count tie), they all sit in the final row.
slots = (maxFreq - 1) * (n + 1) + tie
answer = max(len(tasks), slots)
The max handles the case where there are so many distinct tasks that no idle slot is ever needed; then the answer is simply the number of tasks.
Code
from collections import Counter
def least_interval(tasks, n):
freq = Counter(tasks).values()
max_freq = max(freq)
tie = sum(1 for f in freq if f == max_freq)
return max(len(tasks), (max_freq - 1) * (n + 1) + tie)
Time is O(T) for counting and space O(1), since there are at most 26 task types.
How to explain it out loud
- Draw the frame: write
A _ _ A _ _ Afor n = 2 and show the gaps get filled by other tasks. - Argue why other tasks never make it worse: any task with lower frequency fits into the existing gaps, one per block.
- Mention the heap simulation as an alternative (pop up to n+1 tasks per round, push back decremented counts). It is O(T log 26) and is useful if the interviewer asks for the actual order, not just the length.
Common follow-ups
Interviewers often ask you to output a valid schedule, or to handle a cooldown that differs per task. For the first, use the heap version and record what you pop. For the second, the formula breaks; switch to a simulation with a min-heap keyed by "next available time".
Practice tip
This problem is a good test of whether you can move from simulation to math without losing the interviewer. Say the brute-force idea first, then the observation, then the formula. If you want a second pair of eyes while you rehearse that flow, real-time interview help from an assistant can prompt you when you stall.
Disclosure: I work on Linkjob AI.
Further reading: Linkjob AI resource directory
评论
发表评论