Task Scheduler

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.

Example 1

Input: tasks=["A","A","A","B","B","B"], n=2 → Output: 8

Example 2

Input: tasks=["A","A","A","B","B","B"], n=0 → Output: 6

Solution Approach

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.

Java

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)