Task Scheduler
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
tasks = ["A","A","A","B","B","B"], n = 28A 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
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. Using a max heap to pick the next task and a queue to track cooldowns ensures tasks are scheduled optimally respecting the cooldown constraint.
Optimal Approach
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.
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.
Pattern Spotlight
Greedy Algorithms (Priority Scheduling with Cooldown)
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.
Solution
| 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 |
| 1 | class Solution { |
| 2 | public int leastInterval(char[] tasks, int n) { |
| 3 | int[] count = new int[26]; |
| 4 | for (char task : tasks) { |
| 5 | count[task - 'A']++; |
| 6 | } |
| 7 | PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); |
| 8 | for (int c : count) { |
| 9 | if (c > 0) { |
| 10 | maxHeap.offer(c); |
| 11 | } |
| 12 | } |
| 13 | |
| 14 | int time = 0; |
| 15 | Queue<int[]> q = new ArrayDeque<>(); |
| 16 | |
| 17 | while (!maxHeap.isEmpty() || !q.isEmpty()) { |
| 18 | time++; |
| 19 | if (!maxHeap.isEmpty()) { |
| 20 | int cnt = maxHeap.poll() - 1; |
| 21 | if (cnt > 0) { |
| 22 | q.offer(new int[] {cnt, time + n}); |
| 23 | } |
| 24 | } |
| 25 | |
| 26 | if (!q.isEmpty() && q.peek()[1] == time) { |
| 27 | maxHeap.offer(q.poll()[0]); |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | return time; |
| 32 | } |
| 33 | } |
Step-by-Step Solution
Count Task Frequencies and Initialize Max Heap
| 6 | count = collections.Counter(tasks)
|
| 7 | max_heap = [-c for c in count.values()]
|
| 8 | heapq.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.
Simulate Task Scheduling with Cooldown Queue
| 10 | time = 0
|
| 11 | q = collections.deque()
|
| 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])
|
| 20 | if q and q[0][1] == time:
|
| 21 | heapq.heappush(max_heap, q.popleft()[0])
|
| 23 | return time |
Objective
To simulate the CPU scheduling by incrementing time, scheduling tasks from the heap, and managing cooldowns with a queue.
Key Insight
At each time unit, scheduling the most frequent available task reduces idle time. Tasks that have been scheduled but still have remaining executions are placed in a cooldown queue with the time they become available again. When the cooldown expires, tasks are reinserted into the heap, ensuring the cooldown constraint is respected while maximizing CPU utilization.
Interview Quick-Check
Core Logic
The simulation uses a max heap to pick the next task and a queue to track cooldowns, ensuring tasks are scheduled with at least n units apart.
State & Boundaries
The loop continues until both the heap and cooldown queue are empty, meaning all tasks have been scheduled.
Common Pitfalls & Bugs
Not checking if the cooldown queue's front task is ready to be reinserted at the current time leads to incorrect scheduling and longer total time.
Complexity
Each task is pushed and popped from the heap and queue at most once per execution, maintaining O(T log k) time complexity.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
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.
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.
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.
count = collections.Counter(tasks)Count the frequency of each task using a Counter.
Counting frequencies is essential to identify which tasks constrain the schedule length and to prioritize scheduling accordingly.
q = collections.deque()Initialize a queue to track tasks in cooldown with their next available time.
The cooldown queue enforces the cooldown constraint by delaying re-scheduling of tasks until their cooldown expires.
if q and q[0][1] == time:Check if the front task in the cooldown queue is ready to be rescheduled.
This condition ensures tasks are only reinserted into the heap after their cooldown period has elapsed.
heapq.heappush(max_heap, q.popleft()[0])Reinsert the cooled-down task back into the max heap.
Reinserting the task makes it available for scheduling again, maintaining the greedy selection of the most frequent task.
heapq.heapify(max_heap)Transform the list of negated counts into a heap structure.
Heapifying the list prepares it for efficient push and pop operations, which are critical for the greedy scheduling process.
while max_heap or q:Continue the loop while there are tasks to schedule or tasks cooling down.
The loop ensures all tasks are scheduled and cooldowns are respected before terminating.
q.append([cnt, time + n])Append the task count and its cooldown expiry time to the queue.
Storing the cooldown expiry time allows the algorithm to know when the task can be reinserted into the heap.
return timeReturn the total time elapsed as the minimum schedule length.
The time counter reflects the total units of CPU time needed to complete all tasks respecting cooldown constraints.
time += 1Increment the time counter for each scheduling unit.
Each iteration represents one unit of CPU time, whether executing a task or idling.
if max_heap:Check if there is any task available to schedule.
Only schedule a task if the heap is not empty, ensuring no invalid operations occur.
time = 0Initialize the time counter to zero.
Tracking elapsed time is necessary to measure the total schedule length and to manage cooldown timing.
Test Your Understanding
Why does scheduling the most frequent available task at each time unit guarantee the minimum total time?
Because the task with the highest frequency determines the minimum number of intervals needed to separate identical tasks by the cooldown period. Scheduling it as soon as possible prevents unnecessary idle time, and always picking the most frequent available task ensures the schedule is as compact as possible.
Related Problems
Greedy pattern
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