Untitled

 avatar
unknown
plain_text
2 years ago
1.0 kB
4
Indexable
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {//do the more frequent taks early
        unordered_map<char,int>mp;
        for(char c:tasks) mp[c]++;
        priority_queue<int,vector<int>,less<int>>pq; //task frequency in maxHeap
        for (auto it:mp) pq.push(it.second);

        queue<pair<int,int>>q; //(task freq,time)
        int time=0;
        while(!pq.empty() || !q.empty()){
            time++;
            int freq=0;

            if(!pq.empty()){
                freq =pq.top()-1; //if we pop this our count of the no of taks done increases by 1
                if(freq>0) q.push({freq,time+n}); //after we did this , we can redo this after time +n,only push into queue if freq is larger than 0
                pq.pop(); }
            
            if(!q.empty() && q.front().second<=time){ //we can do the task at front of queue if time is larger than queue time
                pq.push(q.front().first);
                q.pop(); }
        }
        return time;
    }
};
Editor is loading...
Leave a Comment