Task Scheduler Greedy Heap DSA Solution

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.

Input	Output	Why
`tasks = ["A","A","A","B","B","B"], n = 2`	`8`	One valid schedule is A B idle A B idle A B.

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

Step	State	Result
Counts	A:3, B:3	heap has 3 and 3
Cycle 1	Run A, B, then idle	time += 3
Cycle 2	Run A, B, then idle	time += 3
Last cycle	Run A, B	time += 2, total 8

Complexity

Measure	Value	Reason
Time	O(t log u)	t tasks are processed through a heap of u unique task types.
Space	O(u)	The heap and temporary used list store unique task counts.

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

Why choose most frequent tasks first?

They create the most cooldown pressure, so scheduling them early reduces future idle gaps.

Why not always add n + 1?

The final cycle may finish before all cooldown slots are needed.

What is the core pattern?

Greedy scheduling with a max-heap.

Task Scheduler: Greedy Max-Heap Pattern