Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Task Scheduler
• Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Counting

Problem gist

Given a list of CPU tasks and a cooldown n, the scheduler must run every task while making sure two equal task types are separated by at least n time units. In each time unit, the CPU can either execute one task or sit idle. The goal is not to print the schedule; it is to return the smallest possible number of time units needed.

The only hard part is deciding when idle slots are unavoidable. If there are enough other tasks, they can fill the cooldown gaps. If not, the most frequent task forces idle time.

Key idea

Start with the task that appears most often. Suppose the highest frequency is max_count. Those copies create max_count - 1 gaps before the final copy. Each gap must be wide enough to hold n time units before the same task can appear again.

For example, if task A appears four times and n = 2, the skeleton looks like this:

A _ _ A _ _ A _ _ A

That skeleton has (max_count - 1) * (n + 1) + 1 positions when there is only one most-frequent task. If multiple tasks tie for highest frequency, all of them occupy the final group. With A, B, and C each appearing four times, the tail is A B C, so the forced skeleton length becomes:

(max_count - 1) * (n + 1) + number_of_tasks_with_max_count

This is a lower bound because those most frequent tasks cannot be packed closer together. It is also achievable: place the tied most-frequent tasks into the frame first, then use all other tasks to fill the available holes. If the input has enough tasks to fill every hole and then some, the answer is simply len(tasks) because no idle time is needed.

So the optimal answer is:

max(len(tasks), (max_count - 1) * (n + 1) + max_count_task_types)

Python solution

from collections import Counter
from typing import List, Mapping


class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        if not tasks:
            return 0

        task_counts = Counter(tasks)
        cooldown_forced_length = self._minimum_length_for_cooldown(
            task_counts=task_counts,
            cooldown=n,
        )

        # The cooldown frame is the minimum length when idle time is forced.
        # If other tasks fill every gap, the CPU can run continuously instead.
        return max(len(tasks), cooldown_forced_length)

    @staticmethod
    def _minimum_length_for_cooldown(
        task_counts: Mapping[str, int],
        cooldown: int,
    ) -> int:
        highest_frequency = max(task_counts.values())
        most_frequent_task_types = sum(
            1 for count in task_counts.values() if count == highest_frequency
        )

        full_cooldown_frames = highest_frequency - 1
        frame_width = cooldown + 1

        return full_cooldown_frames * frame_width + most_frequent_task_types

The runtime is O(m), where m is the number of tasks, because each task is counted once. The extra space is O(u), where u is the number of distinct task types. For the original LeetCode constraints with uppercase English letters, u is at most 26, so the space is effectively constant.

Why the formula works

The most frequent tasks determine the bottleneck. No matter how clever the order is, two copies of the same most frequent task need n positions between them. That creates a sequence of frames.

Other tasks are flexible filler. They can be placed into the blank positions inside those frames without making the answer longer. If there are more filler tasks than blanks, they spill into positions after the frame, but that still does not create idle time. In that case the schedule length is exactly the number of tasks.

The tie case matters. If both A and B occur three times with n = 2, a valid compact skeleton is:

A B _ A B _ A B

The final group has both max-frequency task types, so the answer uses max_count_task_types, not 1, at the end of the formula.

Interview follow-ups

How would you return one valid schedule instead of only its length?

Use a max heap ordered by remaining count, plus a cooldown queue ordered by the next time a task is allowed to run. At each time unit, move newly available tasks from the cooldown queue back into the heap. If the heap is nonempty, pop the task with the largest remaining count, append it to the schedule, decrement its count, and put it into the cooldown queue if it still has remaining copies. If the heap is empty but the cooldown queue is not, append an idle slot and advance time.

This works because the heap always prioritizes the task type that is currently most likely to cause future idle time. Unlike the closed-form solution, it constructs actual positions, so it naturally handles idle slots and produces a concrete order. The tradeoff is higher complexity: O(T log u) time for a produced schedule of length T, and O(u) extra space.

What changes if every task type has a different cooldown?

The simple formula no longer applies because there is no single frame width. A task with cooldown 10 and a task with cooldown 1 impose very different spacing constraints. The safer approach is simulation with two priority structures: a max heap for currently available tasks by remaining count, and a min heap for cooling tasks by next_available_time.

At each step, release every task whose cooldown has expired, run the available task with the highest remaining count, and then compute that task’s own next available time. This works because the schedule must respect task-specific release times, and the simulation always chooses among exactly the tasks that are legal at the current time. The cost becomes O(T log u), where T includes idle time if the CPU has to wait.

Can the closed-form answer be derived from idle slots instead of frames?

Yes. Treat the most frequent task as creating max_count - 1 gaps. Each gap initially has n empty slots, so there are (max_count - 1) * n slots to fill. If several task types tie for max frequency, those tied tasks occupy one position in each gap except the final tail, reducing the open slots.

Then subtract the counts of all remaining tasks from those open slots. Any slots left over are unavoidable idle time, and the answer is len(tasks) + idle_slots. This is the same reasoning as the frame formula, just viewed from the blanks instead of the occupied positions. It can be easier to explain on a whiteboard, but the frame formula is shorter to implement.

What if there are multiple CPUs that can run tasks in parallel?

The one-CPU formula does not carry over directly. With k CPUs, each time unit can place up to k different runnable tasks, but equal task types still need cooldown separation across all processors. A practical interview answer is to simulate time: keep a max heap of available task types, run up to k distinct available tasks in each tick, then move unfinished tasks into a cooldown queue.

This approach works because each tick makes the best legal use of the processors without running the same task type too early. The complexity is O(T * k * log u) in the direct simulation, where T is the number of time units in the returned schedule. The main tradeoff is that the result depends on constructing the schedule rather than relying on a compact counting formula.

How should the answer change if the input is huge but the task alphabet is small?

Keep the counting solution. The algorithm only needs the frequency of each task type, not the original order, so it can stream through the input once and update a fixed-size counter. After counting, it needs the maximum frequency and the number of task types tied at that maximum.

This works because the original order has no bearing on the minimum schedule length; the scheduler is allowed to reorder tasks freely. For a small alphabet, memory stays constant while runtime remains linear in the number of tasks.