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 _ _ A for 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

评论

此博客中的热门博文

How to Answer "What Motivates You?" in a Job Interview

Cells with Odd Values in a Matrix (LeetCode 1252): Count Rows and Columns, Not Cells