July 23, 2022heap
Problem URL: Task scheduler
We will first count each characters and create a max heap out of it. Then we pop the item from the heap, put it on a queue, and increase the value of our counter. Then we process the task, if there is still task remaining for the same type, we push it back to the heap. After finishing each task, we return the time.
from collections import Counter, deque import heapq from typing import List class Solution: def leastInterval(self, tasks: List[str], n: int) -> int: count = Counter(tasks) maxHeap = [-cnt for cnt in count.values()] heapq.heapify(maxHeap) time = 0 q = deque() while maxHeap or q: time += 1 if not maxHeap: time = q else: cnt = 1 + heapq.heappop(maxHeap) if cnt: q.append([cnt, time+n]) if q and q == time: heapq.heappush(maxHeap, q.popleft()) return time