Task Scheduler

Problem

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. (link)

​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 3^rd interval, neither A nor B can be done, so you idle. By the 4^th 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 <= 10^4

• tasks[i] is an uppercase English letter.

• 0 <= n <= 100

Solution

1. Calculate Frequencies:

   • First, determine the frequencies of all the letters.

2. Significance of ‘n’:

   • If task ‘A’ is currently running, it can only run again after n slots.

   • The distance between consecutive ‘A’ tasks is n (excluding both).

   • Visualize the problem as a set of slots with a size of n+1, referred to as a cycle.

   • In each cycle, any letter can run only once.

   • If ‘A’ runs in the first cycle, it can only run again in the next cycle.

3. Goal:

   • The main goal is to minimize the number of cycles.

   • The minimum number of cycles required is determined by the highest frequency of any task.

   • Always start with the task that has the highest frequency.

   • For example, if the cycle length is n+1 and there are n+1 single tasks with one task ‘A’ repeating twice:

     • In the first n+1 cycle, all single tasks are completed.

     • In the second cycle, ‘A’ runs once, and in the third cycle, ‘A’ runs once again, totaling three cycles with n empty slots in the second and third cycles.

   • By executing the highest frequency task first, we ensure that subsequent cycles are efficiently utilized.

4. Slot Allocation:

   • Allocate slots based on frequency, starting with the highest and moving to the next highest in each cycle.

   • Use a priority queue to manage tasks:

     • In each cycle, remove the highest frequency task, place it in a slot, decrement its frequency by 1, and store it temporarily in list

     • Reinsert the updated frequencies into the priority queue for the next cycle.

5. Cycle Counting:

   • After each cycle, add n+1 to the total steps completed.

   • In the last cycle, it may not occupy all n+1 slots. Use a counter (timer) to track the number of tasks executed.

   • If the priority queue is empty, it indicates that the last cycle has just been completed.

Visualization

Example 1

Example 2

Example 3

class Solution {
    private void addTheTempListBack(List<Integer> temp, PriorityQueue<Integer> pq){
        for(int num: temp){
            if(num!=0) pq.add(num);
        }
    }

    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> map = new HashMap<>();

        for(char task: tasks){
            map.put(task, map.getOrDefault(task, 0)+1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((Integer a, Integer b)-> b-a);

        pq.addAll(map.values());

        int result = 0;
        while(!pq.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int timer = 0; //Timer is only for the last cycle
            for(int i=0; i<=n; i++){

                if(pq.isEmpty()) break;

                int top = pq.poll();
                temp.add(top-1);
                timer+=1;
            }
            addTheTempListBack(temp, pq);
            result += pq.isEmpty() ? timer : n+1;
        }

        return result;
    }
}