621. Task Scheduler

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.

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 <= 104
• tasks[i] is an uppercase English letter.
• 0 <= n <= 100

Solution:

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freqMap = new int[26];
        for (char c : tasks){
            freqMap[c - 'A']++;
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());

        for (int t : freqMap){
            if (t > 0){
                maxHeap.offer(t);
            }
        }

        Queue<int[]> coolingPeriodQueue = new LinkedList<>();

        int time = 0;

        while(!maxHeap.isEmpty() || !coolingPeriodQueue.isEmpty()){
            if (!maxHeap.isEmpty()){
                int t = maxHeap.poll() - 1;
                if (t > 0){
                    coolingPeriodQueue.offer(new int[]{t, time + n});
                }
            }

            if (!coolingPeriodQueue.isEmpty() && coolingPeriodQueue.peek()[1] == time){
                maxHeap.offer(coolingPeriodQueue.poll()[0]);
            }

            time++;
        }

        return time;
    }
}

class Solution {
    public int leastInterval(char[] tasks, int n) {

        // We need to schedule the tasks starting from the task with higher freq first.
        // So we use a max heap to always schedule the max available freq.

        int[] freqMap = new int[26];
        for (char c: tasks) { // We will make the array tasks into a freq map.
            freqMap[c - 'A']++;
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b.compareTo(a));
        for (int t: freqMap) {
            if (t > 0) {
                maxHeap.offer(t);
            }
        }

        // We create a queue to help us to keep the tasks that are in cooling period.
        Queue<int[]> coolingPeriodQueue = new LinkedList<>();
        int time = 0;
        while (!maxHeap.isEmpty() || !coolingPeriodQueue.isEmpty()) {
            if (!maxHeap.isEmpty()) {
                int t = maxHeap.poll() - 1;
                if (t > 0) {
                    coolingPeriodQueue.offer(new int[] {t, time + n});
                }
            }

            if (!coolingPeriodQueue.isEmpty() && coolingPeriodQueue.peek()[1] == time) {
                maxHeap.offer(coolingPeriodQueue.poll()[0]);
            }
            time++; // Every time we schedule a task, one unit of time passes.
        }
        return time;
    }
}


// TC: O(nlogn)
// SC: O(n)