Schedule tasks with a cooldown
Find the shortest time to run all tasks when the same task type must wait a number of slots between runs, by building the plan around the most frequent task. About 22 minutes.
The busiest task sets the frame
Each slot runs one task, and two runs of the same task need at least n other slots between them. Idle slots are allowed. You want the fewest total slots.
Take the task with the highest count, say it runs top times. Its runs cannot be closer than n + 1 slots apart, so top minus one full rows of n + 1 slots, plus a last row holding the final run of each task that ties for most, is a frame you cannot beat.
Fill the gaps or overflow
Other tasks fill the idle spots in the frame. If there are enough of them to fill every gap, nothing is idle, and the total time equals the number of tasks.
If they overflow the frame, you can spread them out so that no two same tasks are close together and still need no idle slots. So the answer is the larger of the frame length and the number of tasks.
top, tied, n = 3, 2, 2 frame = (top - 1) * (n + 1) + tied # 8
A runs. The frame has (3 − 1) rows of 3 slots, plus 1 for the last A: 7 slots.
Tasks A B C D with cooldown 2. What is the shortest time?
- A4
- B6
- C8
Show the answer
4. Every task is different, so no cooldown ever applies.
Task scheduler
You are given a string tasks of uppercase letters, where each letter is a task type, and an integer n. Each task takes one slot. Between two runs of the same task type there must be at least n other slots, which may be idle. Return the fewest slots needed to run all the tasks.
tasks = "AAABBC", n = 2 → 7
1 ≤ tasks.length ≤ 100,000 · uppercase letters only · 0 ≤ n ≤ 100