leetcode

commit c9fc3397fa1bcabe3f1daa8dd5e92de6916f3c90
parent 3a65a9dbdfc3c1a39189d0e3b3f89153f3e6de8f
Author: Andrew Laack <andrew@laack.co>
Date:   Mon,  7 Jul 2025 19:14:41 -0500

Completed task scheduler

Diffstat:
A
task-scheduler/task-schedulerV1.py
 | 
74
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 74 insertions(+), 0 deletions(-)
diff --git a/task-scheduler/task-schedulerV1.py b/task-scheduler/task-schedulerV1.py
@@ -0,0 +1,74 @@
+# Intuition:
+# Use a priority queue where each element
+# has an associated value that states the next
+# time it may be used. The next time it may be used
+# the next one to use is the one that can be used
+# now with the greatest number of values
+# if none can be used now, we wait.
+
+# Approach:
+
+# Time Complexity
+
+# Space Complexity
+
+# Code:
+
+import heapq
+
+# THIS DOESN'T WORK.
+# The issue is that I need to consider when cases where
+# next_valid < current_step because in such cases,
+# it doesn't matter when the next task can be executed, only the count.
+# I tried to add this as a part of lt, but that messes with the heap invariant.
+
+
+# character is not necessary
+class Element:
+    def __init__(self, count, next_valid, character, current_step):
+        self.count = count
+        self.next_valid = next_valid
+        self.character = character
+        self.current_step = current_step
+
+    def __lt__(self, other):
+        if self.next_valid == other.next_valid or (
+            self.current_step[0] < self.next_valid
+            and other.current_step[0] < other.next_valid
+        ):
+            return self.count > other.count
+        return self.next_valid < other.next_valid
+
+    def __repr__(self):
+        return f"Count: {self.count}, Next Valid: {self.next_valid}, Character: {self.character}\n"
+
+
+class Solution:
+    def leastInterval(self, tasks: List[str], n: int) -> int:
+        counts = {}
+        for task in tasks:
+            if task in counts:
+                counts[task] += 1
+            else:
+                counts[task] = 1
+
+        current_step = [0]
+
+        heap = [Element(counts[task], 0, task, current_step) for task in counts]
+
+        while heap:
+
+            current = heapq.heappop(heap)
+
+            if current.next_valid > current_step[0]:
+                current_step[0] = current.next_valid
+
+            current.next_valid = current_step[0] + n + 1
+            current.count -= 1
+
+            if current.count > 0:
+                heapq.heappush(heap, current)
+
+            current_step[0] += 1
+
+        return current_step[0]