C++: Task Scheduler

Thought Process

The problem requires scheduling tasks with a cool down period 'n' between two identical tasks. The key is to maximize efficiency by minimizing idle time. We first calculate the maximum frequency of any task and how many tasks share this frequency. The total intervals required are determined by the formula (mxFreq - 1) * n + mxFreq + cnt - 1, where mxFreq is the maximum frequency and cnt is the count of tasks with that frequency. If the total number of tasks is greater than the calculated intervals, we return the total number of tasks. 

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        
        int mxFreq = 0; // Freq of the most frequent task
        int cnt = 0;  // No. of tasks having this maximum frequency

        map<char,int> mp;
        int totalTasks = tasks.size();
        for(int i=0;i<totalTasks;i++){

            char task = tasks[i];
            mp[task]++;

            if(mp[task]==mxFreq)
                cnt++;

            if(mp[task]>mxFreq){
                cnt = 1;
                mxFreq = mp[task];
            }
        }
        // Tasks that have the same maximum frequency will be put in the last i.e cnt-1
        // (-1 has come because we have already placed one task that have maximum frequency)
        // No of gaps after putting the most frequent task = mxFreq-1
        // Intervals required to place most frequent task  = mxFreq
        int minIntervals = (mxFreq-1)*n + mxFreq + cnt-1;
        
        // If the number of tasks itself is greater than the calculated minIntervals, return totalTasks.
        return max(minIntervals,totalTasks);
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the tasks array once, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, as the map size is limited to the number of unique tasks.

Code copied!