← leetcode

Find Servers That Handled Most Number of Requests

· Hard

LeetCode problem 1606

similar to the problem from two days ago, you have to create a priority_queue for the available and busy servers.

this means that instead of being worst-case time complexity of O(k) for queries and updates, it becomes worst-case O(log(k)), which would make a big difference for values as large as k = 1e5.

the special case we have to consider is that the ith request wants to be handled by the (i % k)th server, and if it's not available, then we check if the (i % k) + 1th server is available, then the (i % k) + 2th server etc. this means a traditional priority_queue would not work, as the (i % k)th server takes priority over the traditionally lower numbered servers. technically, we could solve this by having newly available servers be added to the priority_queue at the end by adding padding (e.g. i + ((j - i) % k + k) % k for server j), but i decided to just use an ordered set, and rely on its lower_bound method to find the next available server.

then, i would simply just collect the counts of all the requests each server would handle, and formulate an ans array.

code link to code

class Solution {
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
        vector<int> requestCount(k, 0);
        vector<int> ids(k);
        iota(ids.begin(), ids.end(), 0);
        
        set<int> available(ids.begin(), ids.end());
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> busy;

        int n {static_cast<int>(arrival.size())};
        for (int i = 0; i < n; ++i) {
            int time {arrival[i]};

            while (!busy.empty() && busy.top().first <= time) {
                available.insert(busy.top().second);
                busy.pop();
            }

            if (available.empty()) continue;

            auto it = available.lower_bound(i % k);
            if (it == available.end()) it = available.begin();

            int server{*it};
            available.erase(it);
            busy.emplace(arrival[i] + load[i], server);
            ++requestCount[server];
        }

        int most {*max_element(requestCount.begin(), requestCount.end())};
        vector<int> ans;

        for (int i = 0; i < k; ++i) {
            if (requestCount[i] == most) {
                ans.push_back(i);
            }
        }

        return ans;
    }
};

complexity link to complexity

  • Time: O(k + n log(k)), where k denotes the number of servers and n denotes the number of requests
  • Space: O(k)

time taken link to time taken

  • 24 minutes and 50 seconds