Medium Greedy + Heap Heaps
In plain English: Schedule tasks so that identical tasks are at least n apart. Find the minimum total time including idle slots.
Greedily schedule the most frequent task first (max-heap). After executing a task, put it on cooldown. Use a queue to track when tasks become available again. Idle when no task is ready.
Prompt
Given a list of tasks (characters) and a cooldown period n, return the minimum number of intervals the CPU needs to finish all tasks. Same tasks must be separated by at least n intervals.
Try to write it from scratch before scrolling down.
Solution
import heapq
from collections import Counter, deque
def least_interval(tasks, n):
counts = Counter(tasks)
heap = [-c for c in counts.values()] # max-heap (negate)
heapq.heapify(heap)
cooldown = deque() # (available_time, remaining_count)
time = 0
while heap or cooldown:
time += 1
if heap:
cnt = heapq.heappop(heap) + 1 # execute one (cnt is negative)
if cnt: # still has remaining executions
cooldown.append((time + n, cnt))
if cooldown and cooldown[0][0] == time:
heapq.heappush(heap, cooldown.popleft()[1])
return time
# Test: least_interval(["A","A","A","B","B","B"], 2) == 8
# A B _ A B _ A B
# Test: least_interval(["A","A","A","B","B","B"], 0) == 6