leetcode

commit 952f59b70f923cbe80b9adae8ae727b46aeb3569
parent c9fc3397fa1bcabe3f1daa8dd5e92de6916f3c90
Author: Andrew Laack <andrew@laack.co>
Date:   Wed,  9 Jul 2025 13:01:18 -0500

Completed task scheduler

Diffstat:
A
task-scheduler/task-schedulerV2.py
 | 
71
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 71 insertions(+), 0 deletions(-)
diff --git a/task-scheduler/task-schedulerV2.py b/task-scheduler/task-schedulerV2.py
@@ -0,0 +1,71 @@
+# Intuition:
+
+# Letters don't matter, only unique groupings
+# at least n intervals between two tasks (cooldown)
+# we want to select the element with the largest count first
+
+# Approach:
+
+# Create a heap with the count of each element
+# NOTE: This should be a max heap which we achieve with * -1 for min-heap in python.
+
+# Main loop
+# check if current len(queue) == n
+# if true then pop current element and add it to the heap
+# Remove the first element from the heap
+# Decrement the element
+# if != 0 add it to a queue
+
+# Time Complexity
+
+# 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.
+
+# Space Complexity
+
+# 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.
+
+# Code:
+
+from collections import deque
+import heapq
+
+
+class Solution:
+    def leastInterval(self, tasks: List[str], n: int) -> int:
+
+        counts_tasks = {}
+
+        for task in tasks:
+            if task in counts_tasks:
+                counts_tasks[task] += 1
+            else:
+                counts_tasks[task] = 1
+
+        counts = [-counts_tasks[ct] for ct in counts_tasks]
+        heapq.heapify(counts)
+
+        # ENCODING:
+        # (COUNT, WHEN_READY)
+
+        queue = deque()
+        itr = 0
+
+        while len(counts) != 0 or len(queue) != 0:
+
+            if queue and queue[-1][1] == itr:
+                to_add = queue.pop()
+                heapq.heappush(counts, to_add[0])
+
+            # queue is not empty, but counts is
+            if len(counts) == 0:
+                itr += 1
+                continue
+
+            next_ele = -heapq.heappop(counts)
+            next_ele -= 1
+            if next_ele != 0:
+                queue.appendleft((-next_ele, itr + n + 1))
+
+            itr += 1
+
+        return itr