LeetCode 1606: Find Servers That Handled Most Number of Requests
Problem Description
Explanation
To solve this problem, we can simulate the process of assigning requests to servers based on the given conditions. We will use two priority queues, one to keep track of available servers and another to keep track of servers that are currently busy. We will iterate through each request, assign it to an available server if possible, update the server's busy time, and move the server from available to busy.
After processing all requests, we will count the number of requests each server handled and find the busiest server(s).
- Time complexity: O(n log k) where n is the number of requests and k is the number of servers
- Space complexity: O(k) where k is the number of servers
Solutions
import java.util.*;
class Solution {
public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
List<Integer> result = new ArrayList<>();
int[] count = new int[k];
PriorityQueue<Integer> available = new PriorityQueue<>();
PriorityQueue<Integer> busy = new PriorityQueue<>();
for (int i = 0; i < k; i++) {
available.offer(i);
}
int n = arrival.length;
int time = arrival[0];
for (int i = 0; i < n; i++) {
time = Math.max(time, arrival[i]);
while (!busy.isEmpty() && arrival[busy.peek()] <= time) {
available.offer(busy.poll());
}
int serverIdx = i % k;
while (!available.isEmpty() && load[i] > 0) {
int server = (serverIdx + available.poll()) % k;
count[server]++;
busy.offer(server);
load[i]--;
}
}
int maxCount = Arrays.stream(count).max().getAsInt();
for (int i = 0; i < k; i++) {
if (count[i] == maxCount) {
result.add(i);
}
}
return result;
}
}Loading editor...