Task Scheduler Cooldown
Problem
A processor runs one task per time slot. Two runs of the same task must be separated by at least gap slots, during which the processor may run a different task or sit idle. Given the list of tasks to run in any order, return the smallest number of slots — busy and idle together — needed to finish them all.
Examples
Input: tasks = ["a", "a", "a", "b", "b", "b"], gap = 2
Output: 8
Why: a b _ a b _ a b fills six tasks into eight slotsInput: tasks = ["a", "a", "a"], gap = 2
Output: 7
Why: a _ _ a _ _ a — nothing else exists to fill the waitsInput: tasks = ["a", "b", "c"], gap = 0
Output: 3
Why: edge case, no cooldown means no idlingHints
0 / 3
The order the tasks are listed in does not matter — only how many times each one appears.
Idle slots appear when the most frequent task is waiting and nothing else is left to run, so that task is the one that shapes the whole schedule.
Work in rounds of gap+1 slots. In each round, take the most frequent remaining tasks first, one per slot, and count the slots you could not fill as idle. Put every task that still has runs left back for the next round.
Solution
Greedily scheduling the most frequent remaining task first is what keeps the busiest task from bunching up at the end, and a max-heap on remaining counts makes that choice cheap. One round is exactly gap + 1 slots, which is the shortest window in which a task may repeat, so filling a round with distinct tasks is always legal. A round that runs out of distinct tasks pays idle slots, except on the final round where the schedule simply ends. Time is O(n log d) for d distinct tasks, space O(d).
import heapq
from collections import Counter
def total_slots(tasks, gap):
heap = [-n for n in Counter(tasks).values()]
heapq.heapify(heap) # max-heap on remaining runs
time = 0
while heap:
held = []
for _ in range(gap + 1): # one cooldown-length round
if heap:
held.append(heapq.heappop(heap) + 1)
time += 1
if not heap and not any(held): # last round: stop, do not idle
break
for n in held:
if n:
heapq.heappush(heap, n)
return time
print(total_slots(["a", "a", "a", "b", "b", "b"], 2)) # -> 8
print(total_slots(["a", "a", "a"], 2)) # -> 7
print(total_slots(["a", "b", "c"], 0)) # -> 3Stuck on the idea rather than the code? Task Scheduler covers it.