Free Heaps lessonsHeaps · Stage 1 · Top k · Step 4

Tasks that need a cool-down

Find the shortest time to finish a list of tasks when the same kind of task must wait n time units between runs, by always running the task with most work left. About 22 minutes.

Run the busiest available

You are given tasks labelled by letters. Running one takes one time unit, and two runs of the same letter must have at least n other time units between them, which may be idle. You want the schedule to end as soon as possible.

A good rule: at each time unit, run a task of the letter that has the most runs left, among the letters that are allowed to run now. A max-heap of the remaining counts gives that letter immediately.

Heap: the remaining counts, biggest first.

Each time unit: run the top one, if any.

In code

c = 1 + heapq.heappop(heap)

Schedule the tasks A, A, A, B, B, B with a cool-down of 2.

idle

A has 3 runs left and B has 3. Run A (a tie, smaller letter first). A must wait 2 units.

Move 1 of 7

The cool-down queue

After running a letter, it has one fewer run left. If runs remain, it cannot run again until n more time units pass, so move it to a waiting queue together with the time when it becomes available.

At every time unit, check the front of the queue. If its time has come, put its count back into the heap. If the heap is empty at some time unit, that unit is idle, and the clock still advances. The answer is the time when both the heap and the queue are empty.

Run it: then queue it until time plus n.

Heap empty: an idle unit; the clock still moves on.

In code

if c:
    cool.append((c, time + n))
if cool and cool[0][1] == time:
    heapq.heappush(heap, cool.popleft()[0])

Quick check

At some time unit every remaining task type is cooling down. What happens?

AThe unit is idle, and the clock advances
BThe schedule is impossible
CThe cool-down is ignored

Show the answer

The unit is idle, and the clock advances. No task can legally run, but time passes.

Your problem

Task scheduler

You are given a string tasks, where each letter is a task of that type, and an integer n. In each time unit you either run one task or stay idle. Two tasks of the same type must be separated by at least n time units. Return the least number of time units needed to finish all the tasks.

Example

tasks = "AAABBB", n = 2 → 8

1 ≤ length of tasks ≤ 10,000 · tasks has only uppercase letters · 0 ≤ n ≤ 100

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.