Heap · Greedy with a cooldown queue

Medium · O(N) time · O(1) space (at most 26 task types)

Problem

You are given an array tasks of capital letters, where each letter is a task type, and an integer n. Each time slot you can run one task or stay idle. Two runs of the same task must have at least n slots between them. Tasks may run in any order. Return the fewest slots needed to finish every task.
Example 1 Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 (A B _ A B _ A B) Example 2 Input: tasks = ["A","A","A","B","B","B"], n = 0 Output: 6 (no cooldown: just run them all)
Constraints 1 ≤ tasks.length ≤ 10^4 tasks[i] is an uppercase English letter 0 ≤ n ≤ 100

Brute force

A computer processor runs one task per time slot. Tasks come in types, shown as letters. After it runs a task of some type, it must wait at least n slots before it may run the same type again. In the meantime it can run other types, or do nothing (stay idle). What is the fewest slots needed to finish all the tasks?

  1. One task per slot, and each copy of a task runs exactly once.
  2. Two runs of the same type must have at least n slots between them.
  3. Idle slots count, so the answer is the number of tasks plus the idle slots we are forced to add.

So the real question is how to avoid idle slots. An idle slot is forced when every task that is left is cooling down. That happens first to the task type with the most copies, because it has the most runs to space out. Here is the schedule for AAABBBC with n = 2, written in rows of n + 1 = 3 slots, because that is how long a task needs before it can run again.

The direct idea: try every order, keeping a table of how long each task type still has to wait, and take the shortest schedule.

The problem with it

The number of orders explodes. For 20 tasks it is already in the billions. We need a rule that picks the right task, instead of searching.

How to think your way to the optimal solution

Which task should run next? The type with the most copies left. That type is the one most likely to cause a forced idle slot later, so we should use up its copies as early as possible. If we leave it until the end, its runs cannot be spaced out, and idle slots are forced. Look at the figure: starting the busiest task late pushes the whole schedule back.

So we need two things at every slot:

At each slot we run the best ready task if there is one. If the heap is empty and the cooling tasks are not ready yet, that slot is idle.

The optimal solution

Approach 1: a heap and a cooldown queue

  1. Count how many copies each task type has, and put the counts in a heap, biggest first.
  2. Each time slot: the heap has a task⟶run the busiest one, and if it has copies left, put it in the cooldown queue with the time it is ready
  3. the heap is empty⟶the slot is idle
  4. If the front of the cooldown queue is ready at this time, put it back in the heap.
  5. Stop when the heap and the queue are both empty. The slot count is the answer.

By hand, with the simpler AAABBB and n = 2. (The player starts with AAABBBC: the extra C simply fills the first idle slot.)

  1. Slot 1: run A (2 copies left). It will be ready at slot 4.
  2. Slot 2: run B (2 left). It will be ready at slot 5.
  3. Slot 3: the heap is empty and nothing is ready: idle.
  4. Slot 4: A is ready again, so run it (1 left). Ready at slot 7.
  5. Slot 5: B is ready, so run it (1 left). Ready at slot 8.
  6. Slot 6: idle.
  7. Slots 7 and 8: run the last A, then the last B.

That is 8 slots: A B _ A B _ A B. Press Play to watch the heap and the cooldown queue.

Approach 2: a formula

The idea. The busiest task type sets the shape of the schedule. Say its count is m. Its runs need m − 1 gaps between them, and each gap, with the run itself, is a row of n + 1 slots. After the last gap there is a final row that holds only the last runs. If k task types tie for the most copies, they all appear in that final row. So the shape is (m − 1) × (n + 1) + k slots, and the other tasks fill the empty spots. If there are so many tasks that they do not all fit, no idle slot is needed, and the answer is simply the number of tasks.

By hand, with AAABBBC and n = 2: the busiest count is 3 (for A and B), so m = 3, and k = 2. The shape is (3 − 1) × 3 + 2 = 8. There are 7 tasks, so the answer is max(7, 8) = 8.

Cost. One pass to count the tasks, so O(N) time and O(1) space (at most 26 types). It gives the length but not the schedule.

Complexity analysis

ApproachTimeSpace
Try every orderexplodesO(N)
Heap and cooldown queueO(N)O(1)
FormulaO(N)O(1)
O(N)
Time (heap). Here's why: N is the number of tasks. There are at most 26 task types, so the heap holds at most 26 items, and a heap step takes a small, fixed time. The schedule has at most N slots plus the idle ones, which is at most about N × (n + 1) in the worst case, so for a fixed n the total is a constant times N.
O(1)
Space. At most 26 types, so the heap and the queue each hold at most 26 items, however many tasks there are.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"Return the actual schedule, not only the number of slots."

What they are checkingWhether you know which of your two solutions can do it. The formula only gives a length.

A strong answerThe formula cannot, but the heap version can. Each slot I write down which task I ran, or an idle mark if I ran none. At the end, that list is the schedule. The time stays the same, and the extra memory is the length of the schedule.

"Explain why the formula works. Where do the idle slots come from?"

What they are checkingWhether you really understand the greedy idea, or have only memorised a formula.

A strong answerThe busiest type needs m − 1 gaps of n slots each between its runs, and that is a hard minimum. The other tasks can fill those gaps. If they fill all of them, there is no idle slot, and the answer is just the number of tasks. If they do not, the empty gaps are idle slots, and the length is the formula. So the answer is the larger of the two: the number of tasks, or the shape set by the busiest type.

"Why a separate cooldown queue? Why not put the task straight back in the heap?"

What they are checkingWhether you understand what the cooldown queue is protecting.

A strong answerIf the task went straight back into the heap, it would be the busiest again, and the next slot would run it again, before its cooldown is over. That breaks the rule. The queue keeps the task out of the heap until its ready time, so the heap holds only tasks that are allowed to run now.

Spot this pattern