task-schedulerV1.py (2071B)
1 # Intuition: 2 # Use a priority queue where each element 3 # has an associated value that states the next 4 # time it may be used. The next time it may be used 5 # the next one to use is the one that can be used 6 # now with the greatest number of values 7 # if none can be used now, we wait. 8 9 # Approach: 10 11 # Time Complexity 12 13 # Space Complexity 14 15 # Code: 16 17 import heapq 18 19 # THIS DOESN'T WORK. 20 # The issue is that I need to consider when cases where 21 # next_valid < current_step because in such cases, 22 # it doesn't matter when the next task can be executed, only the count. 23 # I tried to add this as a part of lt, but that messes with the heap invariant. 24 25 26 # character is not necessary 27 class Element: 28 def __init__(self, count, next_valid, character, current_step): 29 self.count = count 30 self.next_valid = next_valid 31 self.character = character 32 self.current_step = current_step 33 34 def __lt__(self, other): 35 if self.next_valid == other.next_valid or ( 36 self.current_step[0] < self.next_valid 37 and other.current_step[0] < other.next_valid 38 ): 39 return self.count > other.count 40 return self.next_valid < other.next_valid 41 42 def __repr__(self): 43 return f"Count: {self.count}, Next Valid: {self.next_valid}, Character: {self.character}\n" 44 45 46 class Solution: 47 def leastInterval(self, tasks: List[str], n: int) -> int: 48 counts = {} 49 for task in tasks: 50 if task in counts: 51 counts[task] += 1 52 else: 53 counts[task] = 1 54 55 current_step = [0] 56 57 heap = [Element(counts[task], 0, task, current_step) for task in counts] 58 59 while heap: 60 61 current = heapq.heappop(heap) 62 63 if current.next_valid > current_step[0]: 64 current_step[0] = current.next_valid 65 66 current.next_valid = current_step[0] + n + 1 67 current.count -= 1 68 69 if current.count > 0: 70 heapq.heappush(heap, current) 71 72 current_step[0] += 1 73 74 return current_step[0]