Task Scheduler

PracticeNeetCode ↗LeetCode ↗

Given an array of CPU tasks (each represented by a letter) and a cooldown n — the number of full intervals that must pass before the same task letter can run again — return the minimum number of intervals needed to finish all tasks. The CPU can sit idle if no eligible task is available.

Example

Key Pointers

• The most frequent task is the bottleneck — it forces a repeating "frame" of length n + 1 between each of its occurrences.
• If several tasks tie for the highest frequency, each of those needs its own slot in the last frame, which pushes the total up by one per tie.
• When there are enough distinct tasks to fill every idle slot, no idle time is needed at all — the answer can never be less than the array's own length.

Step-by-Step Analysis

1. Count how often each task letter appears.
2. Find maxFreq, the highest count, and maxCount, how many task letters reach that count.
3. Compute the frame-based lower bound: (maxFreq - 1) * (n + 1) + maxCount — the most frequent tasks laid out with mandatory gaps, plus their ties packed into the final frame.
4. Return the larger of that bound and len(tasks), since enough other tasks can fill gaps that would otherwise sit idle.

Complexity

Time: O(n) — Space: O(1) (at most 26 task letters)

Code

from collections import Counter

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

    intervals = (max_freq - 1) * (n + 1) + max_count
    return max(intervals, len(tasks))

Code Explanation

How the solution above works, piece by piece.

1. Only the most frequent tasks can force idle time, so count frequencies.
2. max_freq: the highest count (3). max_count: how many tasks have that count (A and B → 2).
3. Picture max_freq - 1 full blocks of length n + 1, each starting with the most frequent task, plus a final partial row holding the max_count tasks tied for most frequent.
4. Other tasks fill idle slots. If there are more tasks than slots, no idle is needed and the answer is len(tasks), hence the max.
5. O(n) time to count, O(1) space (at most 26 task types).

Visual Walkthrough

Running it on tasks = ["A","A","A","B","B","B"], n = 2:

Video Explanation

NeetCode — LeetCode 621