Task Scheduler
Given an array of tasks an a cooldown period, given an efficient ordering. Tags: Greedy, Priority Queue
Try It!
Discussion
Video
Solution
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
task_counter = {}
for task in tasks:
if task not in task_counter:
task_counter[task] = 0
task_counter[task] += 1
# -count is the way to create max-heap in python. The heapq default is min-heap.
max_heap = []
for task in task_counter:
count = task_counter[task]
heapq.heappush(max_heap, -count)
tot_count = 0
while max_heap:
task_counts = []
for i in range(n + 1):
if max_heap:
count = heapq.heappop(max_heap)
task_counts.append(count)
for task_count in task_counts:
if task_count < -1: # if task_count is equal to -1, it is being used.
heapq.heappush(max_heap, task_count + 1)
if max_heap:
tot_count += n + 1 # + 1 due to difference in indexing +1 for spacing
else:
tot_count += len(task_counts)
return tot_count