Task Scheduler
Problem Description
You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.
Return the minimum number of CPU intervals required to complete all tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.
After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.
Example 2:
Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B.
With a cooling interval of 1, you can repeat a task after just one other task.
Example 3:
Input: tasks = ["A","A","A", "B","B","B"], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B.
There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.
Constraints:
- 1 <= tasks.length <= 104
tasks[i]is an uppercase English letter.0 <= n <= 100
Solve it on LeetCode
Approaches
1. Greedy Scheduling with Priority Queue
Intuition:
The problem can be visualized as filling slots in a schedule but ensuring that there are enough cooldown periods between the same tasks. The most basic approach involves using a priority queue to always schedule the task that is left with the highest frequency. This strategy simulates the task execution by tracking time and rearranging tasks based on cooldowns.
- Frequency Counting: First, calculate the frequency of each task.
- Priority Queue: Use a max heap (priority queue) to always schedule the most frequent task available, as this task contributes the most to minimizing the idle intervals.
- Cooldown Management: Use a cooldown queue to track tasks that are in cooldown periods and need to be paused before they can be scheduled again.
- Time Simulation: Iterate over time units and use steps 2 and 3 above to decide what task, if any, to execute at each time step.
Code:
- Time Complexity: O(N log k), where N is the number of tasks and k is the number of unique tasks.
- Space Complexity: O(N), as we are storing the frequencies and cooldown tasks.
2. Greedy Scheduling with Frequency Calculations
Intuition:
The most optimal solution to this problem is to directly calculate the least interval based on the required cooling periods and the frequencies of the most often appearing tasks. We can use a mathematical approach to determine how to place the tasks efficiently.
- Find Maximum Frequency: Determine the maximum frequency tasks need to be repeated.
- Slots Calculation: Calculate the possible slots needed to place the most frequent tasks and any additional tasks that fit in the gaps.
- Calculate Idle Units: Calculate exactly how many idle units are needed after placing other tasks between the maximum frequency tasks.
- Total Time Calculation: Determine the total required time by summing filled slots and idle time.
Code:
- Time Complexity: O(N), where N is the number of tasks.
- Space Complexity: O(1), only constant extra space is utilized (e.g. for counting frequencies).