Sponsored
Sponsored
This approach involves using a priority queue to manage and track the times when servers become available. Specifically, we will use a heap data structure to efficiently find the first available server for a new request. Whenever a request ends, we reassign the server for future tasks. We also utilize a balanced data structure to cycle through the server indexes and track the server with the most handled requests efficiently.
Time complexity: O(n log k), where n is the number of requests, due to the heap operations. Space complexity: O(k + n) for the heaps and request count.
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <set>
5#include <unordered_map>
6
7using namespace std;
8
9class Solution {
10public:
11 vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
12 set<int> available;
13 for (int i = 0; i < k; ++i) available.insert(i);
14 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;
15 vector<int> requestCount(k, 0);
16 int maxRequests = 0;
17
18 for (int i = 0; i < arrival.size(); ++i) {
19 int time = arrival[i];
20 while (!busy.empty() && busy.top().first <= time) {
21 available.insert(busy.top().second);
22 busy.pop();
23 }
24
25 if (available.empty()) continue;
26
27 auto it = available.lower_bound(i % k);
28 if (it == available.end()) it = available.begin();
29
30 int server = *it;
31 available.erase(it);
32 requestCount[server]++;
33 maxRequests = max(maxRequests, requestCount[server]);
34
35 busy.emplace(time + load[i], server);
36 }
37
38 vector<int> result;
39 for (int j = 0; j < k; ++j) {
40 if (requestCount[j] == maxRequests) {
41 result.push_back(j);
42 }
43 }
44 return result;
45 }
46};In this C++ solution, a `set` is used to maintain available servers while a priority queue tracks when busy servers will be free. The incoming requests calculate which server is available by cycling through the `set` starting from their calculated server index.
The solution uses binary search within the `set` to efficiently allocate servers to requests cyclically.