Task Scheduler
Heaps: lesson 7 of 7
Same greedy pick, but now the loser has to sit out a cooldown.
Lesson 7 of 7 · 7 min
Task Scheduler
Step 1 of 9
Three a, two b, one c — and no task may repeat within 2 seconds of itself.
The Idea
Tasks run one per second, and the same task cannot repeat until the cooldown has passed. Always run whichever task has the most runs left — the scarce resource is time, and that task needs the most of it.
A task that has just run goes into a waiting list stamped with the moment it becomes legal again, then rejoins the heap.
Real-World Example
A gym with one squat rack and a rule that nobody repeats a set without resting. The member with the most sets remaining goes first; everyone else waits out their rest, and the rack idles only when the room runs out of eligible lifters.
The Code
import heapq
from collections import Counter
def schedule(tasks, cooldown):
heap = [-n for n in Counter(tasks).values()]
heapq.heapify(heap) # the busiest task goes first
time, waiting = 0, [] # waiting: (ready_at, runs_left)
while heap or waiting:
time += 1
if waiting and waiting[0][0] <= time:
heapq.heappush(heap, waiting.pop(0)[1]) # its cooldown expired
if heap:
left = heapq.heappop(heap) + 1 # run it once
if left: waiting.append((time + cooldown + 1, left))
return time # idle seconds are counted too
print(schedule(["a", "a", "a", "b", "b", "c"], 2)) # 7
print(schedule(["a", "b", "c", "d"], 2)) # 4 -- enough variety, no idlingYour turn
What does this print?
import heapq
from collections import Counter
heap = [-n for n in Counter("aaabb").values()]
heapq.heapify(heap)
time, waiting = 0, []
while heap or waiting:
time += 1
if waiting and waiting[0][0] <= time:
heapq.heappush(heap, waiting.pop(0)[1])
if heap:
left = heapq.heappop(heap) + 1
if left: waiting.append((time + 3, left))
print(time)Mini quiz
1 / 3