task-schedulerV2.py (1886B)
1 # Intuition: 2 3 # Letters don't matter, only unique groupings 4 # at least n intervals between two tasks (cooldown) 5 # we want to select the element with the largest count first 6 7 # Approach: 8 9 # Create a heap with the count of each element 10 # NOTE: This should be a max heap which we achieve with * -1 for min-heap in python. 11 12 # Main loop 13 # check if current len(queue) == n 14 # if true then pop current element and add it to the heap 15 # Remove the first element from the heap 16 # Decrement the element 17 # if != 0 add it to a queue 18 19 # Time Complexity 20 21 # O(m log k) - for each element we have an insertion into heap, removal (from heap of at most k elements) and decrement, adding to queue, removing from queue, adding to heap. 22 23 # Space Complexity 24 25 # O(n) - The priority queue will have a size of n and thus we must use that amount of space, but the heap is done in place. 26 27 # Code: 28 29 from collections import deque 30 import heapq 31 32 33 class Solution: 34 def leastInterval(self, tasks: List[str], n: int) -> int: 35 36 counts_tasks = {} 37 38 for task in tasks: 39 if task in counts_tasks: 40 counts_tasks[task] += 1 41 else: 42 counts_tasks[task] = 1 43 44 counts = [-counts_tasks[ct] for ct in counts_tasks] 45 heapq.heapify(counts) 46 47 # ENCODING: 48 # (COUNT, WHEN_READY) 49 50 queue = deque() 51 itr = 0 52 53 while len(counts) != 0 or len(queue) != 0: 54 55 if queue and queue[-1][1] == itr: 56 to_add = queue.pop() 57 heapq.heappush(counts, to_add[0]) 58 59 # queue is not empty, but counts is 60 if len(counts) == 0: 61 itr += 1 62 continue 63 64 next_ele = -heapq.heappop(counts) 65 next_ele -= 1 66 if next_ele != 0: 67 queue.appendleft((-next_ele, itr + n + 1)) 68 69 itr += 1 70 71 return itr