We have a set of CPU tasks and a cooldown constraint. After executing a task of type X, we must wait at least n intervals before executing another task of type X. During the wait, we can either execute a different task or sit idle.

The question is: what is the minimum total number of intervals (task executions + idle slots) needed to complete every task?

Here is the key insight. The task that appears most frequently is the bottleneck. If task A appears 6 times and n = 2, then no matter what, we need at least 5 gaps of size (n+1) between consecutive A's, plus the final A itself. Other tasks can fill in those gaps and reduce idle time, but they cannot reduce the minimum imposed by the most frequent task.

So the problem boils down to figuring out how many idle slots the most frequent task forces, and how many of those slots other tasks can fill.

Key Constraints:

Intuition

The most direct way to think about this problem is to simulate the CPU scheduling round by round. At each time step, we want to execute the task that has the highest remaining count, because leaving high-frequency tasks for later increases the chance of forced idle time.

This is a greedy strategy: always pick the most frequent available task. To efficiently find the most frequent task at each step, we can use a max-heap. But there is a catch. After executing a task, it enters a cooldown period and cannot be picked again for the next n intervals. So we need a way to temporarily shelve tasks and bring them back once their cooldown expires.

The approach works like this: use a max-heap to store task frequencies, and a queue to hold tasks that are cooling down along with the time when they become available again. At each time step, pop the most frequent task from the heap, decrement its count, and push it into the cooldown queue with its availability time. When a task in the queue becomes available, move it back to the heap.

Algorithm

a. Increment time

b. If the front of the cooldown queue has an availability time equal to the current time, move that frequency back to the heap

c. If the heap is non-empty, pop the highest frequency, decrement it, and if it is still positive, add it to the cooldown queue with availability time = current time + n + 1

d. If the heap is empty (and we didn't move anything from the queue), this is an idle interval

Example Walkthrough

Code

The simulation approach processes one time step at a time, including idle slots where nothing productive happens. What if we could process entire rounds at once, or even skip the simulation entirely?

Intuition

Instead of simulating each time step, let's think about the problem in rounds. Each round has at most (n + 1) slots. In each round, we pick the tasks with the highest remaining frequencies and execute them. If we don't have enough distinct tasks to fill a round, the remaining slots become idle time.

Think of it like a table with (n + 1) columns. Each row is a round. We fill each row left to right with the most frequent remaining tasks. The number of rows is determined by the frequency of the most common task. The last row might be shorter if some tasks have been fully consumed.

This approach sorts the frequencies repeatedly and processes tasks in chunks of size (n + 1), which is slightly better than step-by-step simulation because we handle an entire round at once.

Algorithm

a. Process one round of at most (n + 1) tasks, picking from most frequent to least

b. Decrement each picked task's frequency

c. Add the number of slots used (tasks + idle) to the time counter

d. Re-sort the frequencies

Example Walkthrough

Code

Both simulation approaches loop through the schedule round by round. Can we compute the answer in a single formula without any looping, using just the frequency distribution?

Intuition

This is the approach interviewers are looking for. Instead of simulating the schedule, we derive a formula.

Consider the task with the highest frequency. Let's call its frequency maxFreq. This task needs to run maxFreq times, and between each consecutive pair of executions, we need at least n intervals of cooldown. So the most frequent task alone creates a framework of (maxFreq - 1) blocks, each of size (n + 1), followed by a final partial block.

Picture it like this. If A appears 3 times and n = 2:

A _ _ | A _ _ | A

That is 2 blocks of 3 slots each, plus a final A. But what if multiple tasks share the maximum frequency? If both A and B appear 3 times:

A B _ | A B _ | A B

The final block now has 2 tasks instead of 1. If maxCount is the number of tasks with frequency equal to maxFreq, the formula becomes: result = (maxFreq - 1) * (n + 1) + maxCount.

There is one more case. When there are many distinct tasks and a small cooldown, the tasks themselves fill more than the formula predicts. So the final answer is: max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount).

Algorithm

Example Walkthrough

Code