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