Task Scheduler: Greedy Max-Heap Pattern

Learning Outcome

After this lesson, you should be able to schedule the most frequent remaining tasks first and avoid overcounting idle time in the last cycle.

Problem Statement

Given tasks and cooldown n, return the least number of intervals needed to finish all tasks.

Brute Force Approach

Try every task order and test cooldown validity. This grows too quickly.

Optimized Approach

Count task frequencies, use a max-heap, and process cycles of length n + 1 by taking the most frequent remaining tasks.

Exact Pseudocode

count task frequencies
heap = max heap of counts
time = 0
while heap is not empty:
  used = []
  slots = 0
  repeat up to n + 1 times while heap has tasks:
    count = pop max - 1
    slots += 1
    if count still positive:
      add count to used
  push used counts back
  if heap is empty:
    time += slots
  else:
    time += n + 1
return time
  

Reference Code

import heapq
from collections import Counter

class Solution:
    def leastInterval(self, tasks, n):
        heap = [-count for count in Counter(tasks).values()]
        heapq.heapify(heap)
        time = 0

        while heap:
            used = []
            slots = 0
            for _ in range(n + 1):
                if heap:
                    count = heapq.heappop(heap) + 1
                    slots += 1
                    if count < 0:
                        used.append(count)
            for count in used:
                heapq.heappush(heap, count)
            time += n + 1 if heap else slots

        return time
  

Sample Dry Run

Complexity

Edge Cases

• If n = 0, answer is the number of tasks.
• The last cycle should not add unnecessary idle time.
• Task order can vary as long as cooldown is valid.

Interview Checklist

• Use max-heap counts, not raw task letters.
• Process at most n + 1 tasks per cycle.
• Only add idle slots when tasks remain after the cycle.

FAQs