Task Scheduler

Problem link - Task Scheduler
You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU 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 intervals 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 interval, 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.
Approach

• One key observation is that the task which appears more frequently needs to be executed first because delaying it causes more idle time, increasing the total time required to execute all tasks. Therefore, we will allow the most frequent task to be executed in the CPU whenever it is permitted, thus minimizing the chances of idle time.
• We will use a Max-Heap to keep track of the most frequent tasks and a map to store the frequency of each task. Every task frequency will be pushed into the Max-Heap.
• Additionally, we will maintain a cooldown queue that stores tasks if there are still instances left to execute. These tasks will be added to the queue along with the remaining executions and the next time when they can be executed.
• Whenever the cooldown period for a particular task expires, it will be removed from the queue and added back to the Max-Heap.
• A timer will count every step, whether it's an executed task or idle time.

    int leastInterval(vector<char>& tasks, int n) {
        priority_queue<int,vector<int>> pq;
        unordered_map<char,int> mp;
        queue<pair<int,int>> cooldown;
        // int maxi=1;
        for(int i=0;i<tasks.size();i++){
            mp[tasks[i]]++;
            // maxi=max(maxi,mp[tasks[i]]);
        }
        for(auto it: mp){
            pq.push(it.second);
            cout<<it.second<<endl;
        }
        int timer=0;
        while(!pq.empty() ||!cooldown.empty()){
            timer+=1;
            if(!pq.empty()){
                int task=pq.top()-1;
                // cout<<task;
                if(task>0){
                    cooldown.push({task,timer+n});
                }
                pq.pop();
            }
            if(!cooldown.empty()){
                if(cooldown.front().second==timer){
                    pq.push(cooldown.front().first);
                    cooldown.pop();
                }
            }

        }
        return timer;

    }

Time complexity:
Main while loop:
The number of iterations the loop runs is equal to the total time required to finish all tasks (including idle times). Hence, O(timer)
Operations inside the loop:
Heap: pop/push operations = O(logk), where k is the length of heap.
Queue operations are O(1)
Overall: O(timer*logk) as the dominant time complexity.

Space complexity:
Overall, space complexity is O(n), where n is the number of unique tasks.
Map: Uses O(n) space to store the frequency of each unique task.
Max Heap: Can hold up to n unique tasks, so its space complexity is O(n).
Cooldown Queue: Similarly, the cooldown queue can hold up to n unique tasks, so it also uses O(n) space.