[621.Task Scheduler] C++_Priority_Queue + Unordered_Map With explanation


  • 0

    This problem is similar with 358. Rearrange String k Distance Apart
    I strongly recommend you to finish that question first before you move on this question.
    My solution for that question: My solution: 358. Rearrange String k Distance Apart

    1. We use map to count the frequencies of each chars in our vector, and use priority queue to sort our pairs according to the chars' frequencies.

    2. For this problem, we use the greedy algorithm. That means when we choose one char, we always try to use the char with the largest frequency among the remaining chars. By this step, we can use the least steps to satisfy the requirements.

    3. While the priority queue is not empty, we choose the top element from the queue, because the distance between two same chars must be n, so we will go to our queue to find out n different chars.

      (a) If there is n different types of chars in our queue, of course, that's perfect, we can deduce 1 from their frequency and then push it into our cache vector if its frequency is not 0.
      (The cache vector will store the pairs from the queue, and then after one round search, we will push the elements in this vector to our priority queue.)

      (b) If there is less n different chars in the queue, then we will use idle. This step is easy.

      So when shall we stop our loop? 1. When the priority queue is empty after one round search. 2. When all of the elements are used up, that's why we use len in our loop as a counter for the number of remaining elements.

    Code:

    class Compare{
    public:
    bool operator()(pair<char, int> a, pair<char, int> b){
        return (a.second < b.second) || (a.second == b.second && a.first > b.first);
    }
    };
    class Solution {
    public:
    int leastInterval(vector<char>& tasks, int n) {
        if(n == 0) return tasks.size();
        unordered_map<char, int> mp;
        int res = 0;
        for(auto c : tasks){mp[c]++;}
        vector<char> vec;
        priority_queue< pair<char, int> , vector< pair<char, int> >, Compare > pq;
        for(auto m : mp){pq.push(m);}
    
        int len = tasks.size();
        while(!pq.empty()){
            vector< pair<char, int> > vec;
            for(int i = 0; i <= n; ++i){//under any circumstance, the distance between the same char should always be n.
                if(len == 0) {return res;}
                if(pq.empty()) {
                    res++;
                }else{
                    auto q = pq.top();
                    pq.pop();
                    res++;
                    if(--q.second > 0){
                        vec.push_back(q);
                    }
                    len--;
                }
            }
            for(auto v : vec){
                pq.push(v);
            }
        }
        return res;
    }
    };

Log in to reply
 

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