Given a char array tasks and integer n (cooldown period), find the minimum number of intervals to execute all tasks. Same tasks must be separated by at least n intervals.
Input: tasks=["A","A","A","B","B","B"], n=2 → Output: 8Input: tasks=["A","A","A","B","B","B"], n=0 → Output: 6
Use a max-heap (by frequency) and a cooldown queue. At each interval, run the most frequent available task. When cooldown expires, re-add task to heap.
- Count frequencies. Add all to max-heap.
- Queue stores (task_freq, available_at_time).
- Each step: if heap non-empty, pop max-freq task, reduce freq, push to queue with available_at = time + n + 1.
- If queue front is available, push back to heap. Increment time.
import java.util.*;
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] freq = new int[26];
for (char c : tasks) freq[c - 'A']++;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int f : freq) if (f > 0) maxHeap.offer(f);
Queue<int[]> cooldown = new LinkedList<>(); // {remaining_freq, available_time}
int time = 0;
while (!maxHeap.isEmpty() || !cooldown.isEmpty()) {
time++;
if (!maxHeap.isEmpty()) {
int f = maxHeap.poll() - 1;
if (f > 0) cooldown.offer(new int[]{f, time + n});
}
if (!cooldown.isEmpty() && cooldown.peek()[1] == time)
maxHeap.offer(cooldown.poll()[0]);
}
return time;
}
}
- Time Complexity: O(N log 26) = O(N)
- Space Complexity: O(26) = O(1)