Getting wrong result with this simple priority_queue approach

  c++, min-heap, priority-queue

I am stuck on this problem I came across on LeetCode https://leetcode.com/problems/process-tasks-using-servers/ and can’t find the error in this approach. I am maintaining two priority queues (min-heaps), where one is storing the busy servers based on the time at which the server would be available and the other is storing the weights and indices of the free servers. Here is my code:

    #define pi pair<int, int>

    class Solution {
    public:
    struct myCmp {
        bool operator()(pi a, pi b) {
            if(a.first == b.first) return (a.second > b.second);
            return (a.first > b.first);
        }
    };
    
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        //pq1 keeps track of the busy servers (It stores the time at which a server would be free and it's index)
        //pq2 keeps track of the available servers (It stores the weight of the server and it's index)
        priority_queue<pi, vector<pi>, greater<pi> > pq1;
        priority_queue<pi, vector<pi>, myCmp> pq2;
        vector<int> res;
        
        for(int i = 0; i<servers.size(); i++) {
            pq2.push(make_pair(servers[i], i));
        }
        
        int i = 0, m = tasks.size(), count = 1, time = 0;
        while(i < m) {
            //Move all the free servers from pq1 to pq2
            while(!pq1.empty() && pq1.top().first == time) {
                pq2.push(make_pair(servers[pq1.top().second], pq1.top().second));
                pq1.pop();
            }
            //If there are no free servers, increase the count (No. of tasks in the queue)
            if(pq2.empty()) count++;
            else {
                //Drecrease count in each loop and move to the next task. Push the index of the server used to the res vector
                while(i < m && !pq2.empty() && count > 0) {
                    pq1.push(make_pair(time+tasks[i], pq2.top().second));
                    res.push_back(pq1.top().second);
                    pq2.pop();
                    count--;
                    i++;
                }
                if(count == 0) count = 1;
            }  
            //Increment time
            time++;
        }
        
        return res;
    }
};

Source: Windows Questions C++

LEAVE A COMMENT