1606. Find Servers That Handled Most Number of Requests

You have k servers numbered from 0 to k-1 that are being used to handle multiple requests simultaneously. Each server has infinite computational capacity but cannot handle more than one request at a time. The requests are assigned to servers according to a specific algorithm:

• The ith (0-indexed) request arrives.
• If all servers are busy, the request is dropped (not handled at all).
• If the (i % k)th server is available, assign the request to that server.
• Otherwise, assign the request to the next available server (wrapping around the list of servers and starting from 0 if necessary). For example, if the ith server is busy, try to assign the request to the (i+1)th server, then the (i+2)th server, and so on.

You are given a strictly increasing array arrival of positive integers, where arrival[i] represents the arrival time of the ith request, and another array load, where load[i] represents the load of the ith request (the time it takes to complete). Your goal is to find the busiest server(s). A server is considered busiest if it handled the most number of requests successfully among all the servers.

Return a list containing the IDs (0-indexed) of the busiest server(s). You may return the IDs in any order.

class Solution {
    vector<int> counter;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> working;
    set<int> servers;
    
    int getServer(int reqId) {
        if(servers.size() == 0) return -1;
        int k = counter.size();
        int serverId = reqId % k;
        auto it = servers.lower_bound(serverId);
        if(it == end(servers)) {
            int server = *servers.begin();
            servers.erase(servers.begin());
            return server;
        } else {
            int server = *it;
            servers.erase(it);
            return server;
        }
    }
    void pushWorkEndServerToServers(int time) {
        while(!working.empty() and working.top().first <= time) {
            servers.insert(working.top().second);
            working.pop();
        }
    }
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
        counter = vector<int>(k,0);
        
        for(int i = 0; i < k; i++) //o(klogk)
            servers.insert(i);
        
        for(int i = 0; i < arrival.size(); i++) {
            pushWorkEndServerToServers(arrival[i]);
            int server = getServer(i);
            if(server == -1) continue;
            counter[server]++;
            working.push({arrival[i] + load[i], server});
        }
        
        vector<int> res;
        int wo = -1;
        for(int i = 0; i < k; i++) {
            if(counter[i] > wo) {
                res.clear();
                wo = counter[i];
                res.push_back(i);
            } else if(counter[i] == wo) {
                res.push_back(i);
            }
        }
        
        return res;
    }
};