📖 6 min read
Last updated on

Task Scheduler — Coding Interview Walkthrough

By intervu.dev

You’re in a coding interview. The interviewer says: “Given a list of CPU tasks and a cooldown interval n, find the minimum time to execute all tasks.” The key insight is that the most frequent task dictates the minimum schedule length; everything else fills in around it. Task Scheduler is LeetCode #621, and it’s a greedy math problem that rewards candidates who can derive a formula rather than simulate every step.

This walkthrough covers both the formula derivation and the heap-based simulation, so you’re prepared no matter which approach the interviewer prefers.

The Problem

You are given an array tasks of CPU tasks, each labeled A to Z. Between two tasks of the same type, there must be at least n intervals of cooldown (idle or other tasks). Return the minimum number of intervals needed to finish all tasks. (LeetCode #621)

Example 1

Input tasks = ["A","A","A","B","B","B"], n = 2

Output 8

Schedule: A -> B -> idle -> A -> B -> idle -> A -> B

Example 2

Input tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2

Output 16

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

Task Scheduler looks like a scheduling simulation but is really a counting problem. Interviewers use it to evaluate whether you can spot the mathematical structure behind a seemingly complex problem.

SkillWhat Interviewers Observe
Greedy insightDo you recognize the formula approach rather than simulating?
Formula derivationCan you derive (max_count - 1) * (n + 1) + max_count_tasks?
Edge case: dense tasksDo you handle the case where len(tasks) > formula?
Frequency countingDo you use a Counter efficiently?
Simulation fallbackCan you implement the heap-based simulation as an alternative?

Step 1: Clarifying Questions

  1. Can n be 0? Yes. No cooldown means tasks run back-to-back in any order. Return len(tasks).

  2. Are all tasks single-character labels? Yes, A to Z. At most 26 distinct task types.

  3. Is there a constraint on the number of tasks? 1 <= len(tasks) <= 10^4.

  4. Does the order of execution matter? No. Only the total number of intervals matters, not the specific schedule.

Step 2: A First (Non-Optimal) Idea

Simulate the schedule step by step: at each time unit, pick the most frequent available task (greedy), decrement its count, and put it on cooldown. If no task is available, idle. This works using a max-heap and a cooldown queue.

import heapq
from collections import Counter, deque

def leastInterval_sim(tasks: list[str], n: int) -> int:
    counts = Counter(tasks)
    max_heap = [-c for c in counts.values()]
    heapq.heapify(max_heap)

    time = 0
    cooldown_queue = deque()  # (time_available, count)

    while max_heap or cooldown_queue:
        time += 1

        if max_heap:
            count = heapq.heappop(max_heap) + 1  # decrement (negated)
            if count < 0:
                cooldown_queue.append((time + n, count))

        if cooldown_queue and cooldown_queue[0][0] == time:
            _, count = cooldown_queue.popleft()
            heapq.heappush(max_heap, count)

    return time
ApproachTimeSpace
Heap simulationO(total_intervals * log 26)O(26) = O(1)
FormulaO(n)O(26) = O(1)

The simulation works but is slower and harder to implement correctly. The formula approach does the same thing in a single pass over the frequency counts.

Step 3: The Key Insight

The most frequent task (call its frequency max_count) dictates the structure of the schedule. It creates max_count - 1 “frames,” each of size n + 1. After the last occurrence of the most frequent task, the schedule ends. The minimum length is (max_count - 1) * (n + 1) + (number of tasks with frequency == max_count). But if there are enough distinct tasks to fill all idle slots, the answer is simply len(tasks).

Visually, for tasks = ["A","A","A","B","B","B"], n = 2:

Frame 1: A B _
Frame 2: A B _
Final:   A B

Three frames of size n + 1 = 3, but the last frame is partial (only the tasks with max frequency). Total: (3-1) * 3 + 2 = 8.

Schedule A B _ A B _ A B showing 8 intervals for tasks [A,A,A,B,B,B] with n=2 cooldown. A tasks highlighted in teal. ---

Step 4: Formula Derivation

Let max_count = max frequency of any task, max_count_tasks = number of task types with that frequency.

  1. The most frequent task creates max_count - 1 full frames of size n + 1.
  2. The final partial frame contains one slot for each task type that has max_count.
  3. Formula: (max_count - 1) * (n + 1) + max_count_tasks.
  4. But if tasks are dense enough (many distinct types), no idle slots are needed.
  5. Final answer: max((max_count - 1) * (n + 1) + max_count_tasks, len(tasks)).

Python Implementation

from collections import Counter

def leastInterval(tasks: list[str], n: int) -> int:
    counts = Counter(tasks)
    max_count = max(counts.values())
    max_count_tasks = sum(1 for c in counts.values() if c == max_count)

    formula = (max_count - 1) * (n + 1) + max_count_tasks
    return max(formula, len(tasks))

Why this is interview-friendly:

  • Four lines of logic. Count frequencies, find the max, count how many tasks share that max, apply the formula. Clean and auditable.
  • No simulation needed. The formula captures the entire scheduling structure without stepping through time units.
  • The max() at the end handles the dense case. When there are so many distinct tasks that all idle slots get filled, the answer is just len(tasks).

Time & Space Complexity

TimeSpace
FormulaO(n)O(26) = O(1)
Heap simulationO(total_intervals * log 26) = O(n)O(26) = O(1)

Both are effectively O(n) with O(1) space since the alphabet is fixed at 26 characters.

Common Interview Mistakes

  1. Forgetting max(formula, len(tasks)). When there are many diverse tasks, idle slots disappear entirely. The formula can undercount. Always cap it at len(tasks).

  2. Not counting tasks with max_count correctly. If both A and B appear 3 times and n = 2, the last frame has both A and B, not just one. max_count_tasks must count how many task types share the maximum frequency.

  3. Simulating per-step without a heap. Greedy simulation without a priority queue runs in O(n * 26) per time unit, is harder to implement, and more error-prone.

  4. Confusing n with n+1. The frame size is n + 1 (the task itself plus n cooldown slots), not n. This off-by-one changes the entire formula.

What a Strong Candidate Sounds Like

“The minimum schedule is anchored by the most frequent task. It creates max_count - 1 full frames of size n + 1, then a final partial frame with all tasks that have the max frequency. The formula is (max_count - 1) * (n + 1) + max_count_tasks. But if the tasks are dense enough to fill all idle slots, we just return len(tasks). So the answer is max(formula, len(tasks)).”

Example Interview Dialogue

Interviewer: Walk through ["A","A","A","B","B","B"], n=2.

Candidate: max_count = 3 (both A and B appear 3 times). max_count_tasks = 2. Formula: (3-1) * (2+1) + 2 = 6 + 2 = 8. len(tasks) = 6. Answer is max(8, 6) = 8. The schedule looks like A B _ | A B _ | A B. That’s 8 slots.

Interviewer: What about n=0?

Candidate: Frame size is n + 1 = 1. Formula becomes (max_count - 1) * 1 + max_count_tasks. For AAA BBB: (3-1)*1 + 2 = 4. But len(tasks) = 6. Answer is max(4, 6) = 6. With no cooldown, we just run all tasks back-to-back.

Interviewer: When does the formula undercount?

Candidate: When there are enough distinct task types to fill every idle slot. For example, tasks = ["A","A","A","B","C","D","E","F","G"], n = 2. Formula: (3-1) * 3 + 1 = 7. But len(tasks) = 9. There are so many tasks that the schedule needs no idle time at all. Answer is 9.

Practice This in a Mock Interview

Task Scheduler is a problem where the formula approach is far superior to simulation, but you need to understand why the formula works, not just memorize it. Being able to derive (max_count - 1) * (n + 1) + max_count_tasks from first principles, draw the frame structure, and handle the len(tasks) edge case is what makes a strong answer.

Start a mock interview for Task Scheduler on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →