How do you solve Task Scheduler?

Count the frequency of each task and build a max heap of negative counts to simulate a priority queue of tasks by remaining frequency. At each time unit, pop the most frequent task from the heap, schedule it (decrement count), and if it still has remaining executions, add it to a cooldown queue with the time it becomes available again (current time + n). When the cooldown expires, reinsert the task into the heap. Continue until both the heap and cooldown queue are empty. The total time elapsed is the minimum schedule length.

What pattern does Task Scheduler use?

The Pattern: Greedy Algorithms (Priority Scheduling with Cooldown) The Heuristic: Always schedule the task with the highest remaining frequency available to minimize idle time, and use a cooldown queue to enforce the cooldown constraint, ensuring tasks are spaced optimally without unnecessary delays.

Task Scheduler — Greedy Algorithms

Q: What is the time complexity of Task Scheduler?

O(T log k). Where T is the total number of tasks and k is the number of unique tasks. Each task is pushed and popped from the heap at most once per execution, and heap operations take O(log k) time.

Problem

Given a list of tasks represented by characters and a non-negative integer n representing the cooldown period between two same tasks, return the least number of units of time the CPU will take to finish all the tasks such that the same task is separated by at least n units of time.

1 ≤ tasks.length ≤ 10⁴
tasks[i] is an uppercase English letter.
The integer n is in the range [0, 100].

Example

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

A brute-force approach would try to schedule tasks one by one, inserting idle times as needed, which is inefficient. The optimal strategy uses a greedy approach based on task frequencies and cooldown constraints. The algorithm counts the frequency of each task: A and B both appear 3 times. It uses a max heap to always pick the task with the highest remaining count to schedule next. After scheduling a task, it must wait for n units before scheduling the same task again, so the task is placed in a cooldown queue with the time it becomes available again. At each time unit, the algorithm increments time, schedules a task if available, and checks if any tasks in cooldown can be re-added to the heap. This process continues until all tasks are scheduled. The core insight is that by always scheduling the most frequent available task and enforcing cooldowns via a queue, the algorithm minimizes idle time and guarantees the shortest schedule length.

Approach

Straightforward Solution

A naive approach simulates the schedule by placing tasks and inserting idle times as needed, which can be inefficient and complex to implement, especially for large inputs.

Core Observation

The minimum schedule length depends on the task with the highest frequency because it dictates the minimum number of intervals needed to separate identical tasks by at least n units.

Path to Optimal

Preview

The key recognition signals are 'minimum time to finish tasks with cooldown' and 'tasks represented by characters with frequencies'. These indicate a Greedy Algorithm because the problem reduces to always scheduling the most frequent available task to minimize idle time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Count the frequency of each task and build a max heap of negative counts to simulate a priority queue of tasks by remaining frequency…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(T log k)

Where T is the total number of tasks and k is the number of unique tasks. Each task is pushed and popped from the heap at most once per execution, and heap operations take O(log k) time.

Space

O(k)

The heap and cooldown queue store at most k unique tasks, where k is the number of distinct task types.

Solution

Python

1import collections
2import heapq
3
4class Solution:
  def leastInterval(self, tasks: list[str], n: int) -> int:
      count = collections.Counter(tasks)
      max_heap = [-c for c in count.values()]
      heapq.heapify(max_heap)
9
      time = 0
      q = collections.deque()
12
      while max_heap or q:
          time += 1
          if max_heap:
              cnt = 1 + heapq.heappop(max_heap)
              if cnt:
                  q.append([cnt, time + n])
          
          if q and q[0][1] == time:
              heapq.heappush(max_heap, q.popleft()[0])
      
      return time

Step-by-Step Solution

1

Count Task Frequencies and Initialize Max Heap

6count = collections.Counter(tasks)
7max_heap = [-c for c in count.values()]
8heapq.heapify(max_heap)

Objective

To count how many times each task appears and prepare a max heap to always select the task with the highest remaining count.

Key Insight

Counting frequencies identifies the tasks that will most constrain the schedule length. Using a max heap of negative counts allows efficient retrieval of the task with the highest remaining frequency, which is critical for the greedy scheduling strategy.

Interview Quick-Check

Core Logic

Counting task frequencies and using a max heap enables efficient selection of the next task to schedule based on highest remaining count.

Common Pitfalls & Bugs

Forgetting to negate counts for the max heap in Python leads to incorrect priority ordering since heapq is a min-heap by default.

2

Simulate Task Scheduling with Cooldown Queue

To simulate the CPU scheduling by incrementing time, scheduling tasks from the heap, and managing cooldowns with a queue.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 7 Critical

max_heap = [-c for c in count.values()]

Create a max heap by negating the counts of each task.

Python's heapq is a min-heap, so negating counts allows it to function as a max heap, enabling efficient retrieval of the most frequent task.

Line 16 Critical

cnt = 1 + heapq.heappop(max_heap)

Pop the most frequent task from the heap and decrement its count.

Scheduling the most frequent task first minimizes idle time and respects the greedy strategy.

Line 17 Critical

if cnt:

If the task still has remaining executions, add it to the cooldown queue with its next available time.

Placing the task in cooldown enforces the required separation between identical tasks, preventing premature re-scheduling.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why does scheduling the most frequent available task at each time unit guarantee the minimum total time?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Task Scheduler from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Task Scheduler drill

or drill a free problem

1	`import collections`
2	`import heapq`
3
4	`class Solution:`
5	`def leastInterval(self, tasks: list[str], n: int) -> int:`
6	`count = collections.Counter(tasks)`
7	`max_heap = [-c for c in count.values()]`
8	`heapq.heapify(max_heap)`
9
10	`time = 0`
11	`q = collections.deque()`
12
13	`while max_heap or q:`
14	`time += 1`
15	`if max_heap:`
16	`cnt = 1 + heapq.heappop(max_heap)`
17	`if cnt:`
18	`q.append([cnt, time + n])`
19
20	`if q and q[0][1] == time:`
21	`heapq.heappush(max_heap, q.popleft()[0])`
22
23	`return time`