Skip to content

Instantly share code, notes, and snippets.

@Chinwendu20
Created September 10, 2023 16:23
Show Gist options
  • Save Chinwendu20/6966d650d2979aec45c44063aac77f74 to your computer and use it in GitHub Desktop.
Save Chinwendu20/6966d650d2979aec45c44063aac77f74 to your computer and use it in GitHub Desktop.
Neetcode's solution task scheduler
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
s = Counter(tasks)
# {A: 3, B: 3}
maxHeap = [-i for i in s.values()] #xxxxxxxx
# s.values() = [3, 3]
heapq.heapify(maxHeap)
# heapq.heapify(s.values())
time = 0
q = deque()
while maxHeap or q:
time = time+1
if maxHeap:
cnt = 1 + heapq.heappop(maxHeap)
# cnt = heapq.heappop(maxHeap) - 1
# cnt = 2
if cnt:
q.append([cnt, time+n])
# q.append([2, 1+2])
# q = [[2, 3], [2, 4]]
if q and q[0][1] == time :
heapq.heappush(maxHeap, q.popleft()[0])
return time
# Iter 3
# time = 3
# maxHeap=[]
# if maxHeap: xxxxxxxx
# if q and q[0][1] == time : >>>>>
# q = [[2, 3], [2, 4]]
# q[0] = [2, 3]
# q[0][1] = 3
# Push into maxHeap
# maxHeap = [2]
# Iter 4
# time = 4
# maxHeap=[2]
# if maxHeap: >>>>>
# maxHeap = []
# cnt = 2 -1 = 1
# [[2, 4], [1, 4+2]]
# if q and q[0][1] == time : >>>>>
# q[0] = [2, 4]
# q[0][1] = 4
# Push into maxHeap
# maxHeap = [2]
# q = [[1, 6]]
# Iter 5
# time = 5
# maxHeap=[2]
# if maxHeap: >>>>>
# maxHeap = []
# cnt = 2 -1 = 1
# [[2, 4]]
# if q and q[0][1] == time : >>>>>
# q[0] = [2, 4]
# q[0][1] = 4
# Push into maxHeap
# maxHeap = [2]
# q = [[1,6], [1,7]]
#
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment