1606. Find Servers That Handled Most Number of Requests

2026, Nov 08 2 mins read

1. Description

There are k servers numbered 0 through k - 1, each handling at most one request at a time.
Request i arrives at arrival[i] and takes load[i] time units. The arrival times are strictly increasing.
Assign each request to the first available server starting from i % k, checking increasing server IDs and wrapping around to 0. Drop the request if all servers are busy.
A server finishing at time t can accept a request arriving at t.
Return the IDs of all servers that handle the most requests, in any order.

2. Example

Example 1

Input: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]
Output: [1]
Explanation: Server 1 handles two requests; servers 0 and 2 handle one each. The last request is dropped.

Example 2

Input: k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
Explanation: Server 0 handles two requests, while each other server handles one.

Example 3

Input: k = 3, arrival = [1,2,3], load = [10,12,11]
Output: [0,1,2]
Explanation: Each server handles one request.

3. Constraints

1 <= k <= 10$^5$
1 <= arrival.length, load.length <= 10$^5$
arrival.length == load.length
1 <= arrival[i], load[i] <= 10$^9$
arrival is strictly increasing.

4. Solutions

Ordered Set && Min-Heap

n = arrival.size(), k = number of servers
Time complexity: O((n + k) log k)
Space complexity: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    vector<int> busiestServers(int k, vector<int> &arrival, vector<int> &load) {
        const int n = arrival.size();

        set<int> available_servers;
        for (int i = 0; i < k; ++i) {
            available_servers.insert(i);
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> scheduled_tasks;
        vector<int> request_count(k, 0);

        int max_request = 0;
        for (int i = 0; i < n; ++i) {
            while (!scheduled_tasks.empty() && scheduled_tasks.top().first <= arrival[i]) {
                available_servers.insert(scheduled_tasks.top().second);
                scheduled_tasks.pop();
            }

            if (available_servers.empty()) {
                continue;
            }

            auto iter = available_servers.lower_bound(i % k);
            if (iter == available_servers.end()) {
                iter = available_servers.begin();
            }

            int server = *iter;
            available_servers.erase(iter);

            scheduled_tasks.emplace(arrival[i] + load[i], server);
            max_request = max(max_request, ++request_count[server]);
        }

        vector<int> max_request_servers;
        for (int i = 0; i < k; ++i) {
            if (request_count[i] == max_request) {
                max_request_servers.push_back(i);
            }
        }

        return max_request_servers;
    }
};

Search

Tags