C++ solution with comments to help understand the logic


  • 0
    G
    class Solution {
    public:
        
        struct Elm{
            char chr;
            int count;
            int next;
            
            Elm():
                chr('0'),count(0),next(-1){}
            
            Elm(char c, int cnt, int n):
                chr(c),count(cnt),next(n){}
            
            Elm& operator=(const Elm& other){
                chr = other.chr;
                count = other.count;
                next = other.next;
                return *this;
            }
            
            Elm(const Elm& e)
                :
                chr(e.chr),
                count(e.count),
                next(e.next){}
        };
        
        struct Comp{
            bool operator()(const Elm *e1, const Elm *e2){
                if(e1->count < e2->count){
                    return true;
                }
                else if(e1->count == e2->count){
                    return e1->chr < e2->chr;
                }
                
                return false;
            }
        };
        
        int leastInterval(vector<char>& tasks, int n) {
                
                //max heap based on number of occurances of each char
                priority_queue<Elm*,vector<Elm*>,Comp> pq;
            
                // wait Q - holds elements until its their turn to go 
                deque<Elm*> q;
            
                //the current insertion index into the solution
                int currIdx = 0;
            
                //counting map 
                unordered_map<char,int> m;
                
                //count occurances of each task 
                for(auto &c : tasks){
                    m[c]++;
                }
                
                // generate Elm pointers for each task
                for(auto &p : m){
                    Elm *e = new Elm(p.first,p.second,0);
                    pq.push(e);
                }
            
                //so long as we have tasks to process
                while(!pq.empty() || !q.empty()){
    
                    //first see if the waiting q has elements that need be added
                    // to the heap
                    while(!q.empty()){
    
                        if(q.front()->next > currIdx){
                            if(pq.empty()){
                                currIdx++;
                            }
                            else{
                                break;
                            }
                        }
                        else{
                            pq.push(q.front());
                            q.pop_front();
                        }
                    }
                    
                    //take out the highest count element from the heap
                    auto top = pq.top();
                    pq.pop();
                    
                    //update its next to be scheduled & its count
                    top->next = currIdx + n + 1;
                    top->count--;
                 
                    //if the count is still positive insert it to the wait q
                    if(top->count > 0){
                        q.push_back(top);
                    }
                    
                    currIdx++;
                }
                    
            return currIdx;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.