Core Insight Keep only candidates that may become the next answer, ordered by the priority that matters.
Common Pitfall Push only meaningful candidates and remove stale entries before trusting the root.
Description
Return the minimum intervals to execute all tasks.
Constraints
- Time Complexity:
O(n log n) - Space Complexity:
O(n)
Tags
arrayhash-tablegreedysortingheapcounting
Implementation Plan Translate the invariant into these small, testable moves.
- Choose the priority key.
- Push initial candidates.
- Pop the best valid candidate.
- Add newly eligible candidates and repeat.
def leastInterval(tasks, n):
count = collections.Counter(tasks)
maxHeap = [-cnt for cnt in count.values()]
heapq.heapify(maxHeap)
time = 0
q = collections.deque()
while maxHeap or q:
time += 1
if maxHeap:
cnt = 1 + heapq.heappop(maxHeap)
if cnt:
q.append([cnt, time + n])
if q and q[0][1] == time:
heapq.heappush(maxHeap, q.popleft()[0])
return time