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.
1import java.util.*;
2
3class Solution {
4 public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
5 PriorityQueue<Integer> available = new PriorityQueue<>();
6 TreeMap<Integer, Integer> busy = new TreeMap<>();
7 int[] requestCount = new int[k];
8 int maxRequests = 0;
9
10 for(int i = 0; i < k; i++) available.add(i);
11
12 for(int i = 0; i < arrival.length; i++) {
13 int time = arrival[i];
14 while(!busy.isEmpty() && busy.firstKey() <= time) {
15 available.add(busy.pollFirstEntry().getValue());
16 }
17
18 if(available.isEmpty()) continue;
19
20 int index = i % k;
21 Integer server = available.ceiling(index);
22 if(server == null) server = available.first();
23
24 available.remove(server);
25 requestCount[server]++;
26 maxRequests = Math.max(maxRequests, requestCount[server]);
27 busy.put(time + load[i], server);
28 }
29
30 List<Integer> result = new ArrayList<>();
31 for(int j = 0; j < k; j++) {
32 if(requestCount[j] == maxRequests) {
33 result.add(j);
34 }
35 }
36 return result;
37 }
38}This Java solution uses a priority queue to manage available servers and a TreeMap to track busy servers and their completion times. It processes each request by finding the next available server that is free at the given request time or will be immediately after.
The algorithm considers server indexes cyclically, using ceiling search and defaulting to the smallest available index if needed.