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 <= 104tasks[i] is an uppercase English letter.0 <= n <= 100The key idea is to figure out the task with the maximum frequency and set its intervals accordingly.
Assume the task with the highest frequency appears max_count times. Arrange tasks such that the remaining tasks are fitted in between the most frequent task considering the cooldown period.
The formula for the minimum intervals required is determined by the max frequency task with necessary slots due to the cooling period. The result is the maximum of the total tasks or the formed slots, i.e., max(len(tasks), (max_count - 1) * (n + 1) + count_max), where count_max is the number of tasks with frequency equal to max_count.
This C solution computes the frequency of each task using an array of size 26. It calculates the maximum frequency and the number of tasks with this frequency. The least number of intervals is calculated using the formula discussed.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of tasks. Space Complexity: O(1), as the space for the frequency array is constant.
Another way is to simulate the task processing using a priority queue to always pick the task with the highest remaining count that can be scheduled. A min-heap or a max-heap is useful to efficiently get the next task. As tasks are being processed, they are placed on cooldown before they can be executed again, managed by a cooldown queue.
This C solution uses sorting as an auxiliary step to simulate the behavior of a priority queue. The task processing works by repeatedly selecting the most frequent task, calculating available idle slots, and filling them as necessary.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N log N), where N is determined by sorting. Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Max Frequency Task-based approach | Time Complexity: O(N), where N is the number of tasks. Space Complexity: O(1), as the space for the frequency array is constant. |
| Priority Queue (Heap)-based Simulation | Time Complexity: O(N log N), where N is determined by sorting. Space Complexity: O(1). |
Task Scheduler - Leetcode 621 - Python • NeetCode • 221,352 views views
Watch 9 more video solutions →Practice Task Scheduler with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor