621. Task Scheduler
## description
## 621. Task Scheduler
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.
- –1 <= tasks.length <= 104
- –tasks[i] is an uppercase English letter.
- –0 <= n <= 100
Constraints:
## notes
### Intuition
To minimize total time, we should always execute the most frequent remaining task. When all available tasks are cooling down, we must idle until one becomes ready. A max heap lets us greedily pick the most frequent task at each step, and a cooldown queue tracks tasks waiting to be re-added.
### Implementation
Count task frequencies, then build a max heap from the counts (negated for Python's min heap).
Maintain a cooldown_q deque of (remaining_count, available_at_time) pairs. Simulate time t:
- –Each loop iteration increments t by 1.
- –If the heap is empty (all tasks cooling down), jump t directly to cooldown_q[0][1] to skip idle time.
- –Otherwise, pop the most frequent task, decrement its count, and if it still has remaining executions, append (count, t + n) to the cooldown queue.
- –After processing, if the front of the cooldown queue has available_at_time == t, pop it and push its count back onto the heap.
Return t when both the heap and cooldown queue are empty.
### Edge-cases
When the heap is empty but the cooldown queue is non-empty, jumping t directly to cooldown_q[0][1] avoids simulating each idle tick individually—but we still only do this when the heap is empty, since if tasks are available we should execute them instead.
- –Time: O(n) where n is total number of tasks. Heap operations are constant because the heap will be at most 26 values.
- –Space: O(1), heap size is, at most, 26 values.
### Complexity
## solution
1from typing import List
2import heapq
3from collections import defaultdict, deque
4
5class Solution:
6 def leastInterval(self, tasks: List[str], n: int) -> int:
7 freq = defaultdict(int)
8 for task in tasks:
9 freq[task] += 1
10
11 max_heap = [-f for f in freq.values()]
12 heapq.heapify(max_heap)
13
14 cooldown_q = deque([])
15 t = 0
16 while max_heap or cooldown_q:
17 t += 1
18 if not max_heap:
19 t = cooldown_q[0][1]
20 else:
21 count = -heapq.heappop(max_heap)
22 count -= 1
23 if count:
24 cooldown_q.append((count, t + n))
25 if cooldown_q and cooldown_q[0][1] == t:
26 heapq.heappush(max_heap, -cooldown_q.popleft()[0])
27 return t
28
29if __name__ == "__main__":
30 # Include one-off tests here or debugging logic that can be run by running this file
31 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
32 solution = Solution()
33