Problem Statement
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of 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 cycles 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 cycle, 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.
Try here before watching the video.
Video Explanation
Java Code
class Solution {
public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> frequencyMap = new HashMap<>();
for(char task : tasks) {
frequencyMap.put(task, frequencyMap.getOrDefault(task, 0) + 1);
}
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
maxHeap.addAll(frequencyMap.entrySet());
int intervals = 0;
while(!maxHeap.isEmpty()) {
int coolDownPeriod = n + 1;
Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
while(!maxHeap.isEmpty() && coolDownPeriod > 0) {
Map.Entry<Character, Integer> entry = maxHeap.poll();
entry.setValue(entry.getValue() - 1);
intervals += 1;
if(entry.getValue() != 0) {
queue.add(entry);
}
coolDownPeriod -= 1;
}
if(queue.size() != 0) {
maxHeap.addAll(queue);
intervals += coolDownPeriod;
}
}
return intervals;
}
}
C++ Code
class Solution {
public:
struct comparator {
bool operator() (pair<char, int> &x, pair<char, int> &y) {
return y.second > x.second;
}
};
int leastInterval(vector<char>& tasks, int n) {
unordered_map<char, int> frequencyMap;
for (char task : tasks) {
frequencyMap[task]++;
}
priority_queue<pair<char, int>, vector<pair<char, int>>, comparator> maxHeap;
for (auto& entry : frequencyMap) {
maxHeap.push({entry.first, entry.second});
}
int intervals = 0;
while (!maxHeap.empty()) {
int cooldownPeriod = n + 1;
queue<pair<char, int>> queue;
while (!maxHeap.empty() && cooldownPeriod > 0) {
auto entry = maxHeap.top();
maxHeap.pop();
entry.second--;
intervals++;
if (entry.second != 0) {
queue.push(entry);
}
cooldownPeriod--;
}
if (!queue.empty()) {
while (!queue.empty()) {
maxHeap.push(queue.front());
queue.pop();
}
intervals += cooldownPeriod;
}
}
return intervals;
}
};
Python Code
from collections import Counter
import heapq
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
frequency_map = Counter(tasks)
max_heap = [(-count, task) for task, count in frequency_map.items()]
heapq.heapify(max_heap)
intervals = 0
while max_heap:
cooldown_period = n + 1
queue = []
while cooldown_period > 0 and max_heap:
count, task = heapq.heappop(max_heap)
count += 1
intervals += 1
if count != 0:
queue.append((count, task))
cooldown_period -= 1
if queue:
intervals += cooldown_period
for item in queue:
heapq.heappush(max_heap, item)
return intervals
Go Code
type Entry struct {
task byte
count int
}
type MaxHeap []Entry
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].count > h[j].count }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(Entry)) }
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func leastInterval(tasks []byte, n int) int {
frequencyMap := make(map[byte]int)
for _, task := range tasks {
frequencyMap[task]++
}
maxHeap := &MaxHeap{}
for task, count := range frequencyMap {
heap.Push(maxHeap, Entry{task, count})
}
intervals := 0
for len(*maxHeap) > 0 {
cooldownPeriod := n + 1
queue := []Entry{}
for cooldownPeriod > 0 && len(*maxHeap) > 0 {
entry := heap.Pop(maxHeap).(Entry)
entry.count--
intervals++
if entry.count > 0 {
queue = append(queue, entry)
}
cooldownPeriod--
}
if len(queue) > 0 {
intervals += cooldownPeriod
for _, entry := range queue {
heap.Push(maxHeap, entry)
}
}
}
return intervals
}
Complexity Analysis
Time Complexity: O(N)
In the worst case, all tasks must be processed, and each task might be inserted and extracted from the priority queue. The priority queue operations (insertion and extraction) have a time complexity of O(logk) each. Therefore, the overall time complexity is O(N * logk). Since k is at maximum 26, logk is a constant term. We can simplify the time complexity to O(N). This is a linear time complexity with a high constant factor.
Space Complexity: O(1)
The space complexity is mainly determined by the frequency array and the priority queue. The frequency array has a constant size of 26, and the priority queue can have a maximum size of 26 when all distinct tasks are present. Therefore, the overall space complexity is O(1) or O(26), which is considered constant.