1606. Find Servers That Handled Most Number of Requests
- Array
- Heap (Priority Queue)
- Simulation
Intuition
Each request needs two things fast: release the servers whose work has finished, and find the first free server going clockwise from i % k. The first is a min-heap on end time. The second is usually an ordered set with a ceiling lookup plus a wrap-around, but a plain min-heap also works if each free server is stored under a shifted key instead of its id.
When server id becomes free during request i, store it as i + (id - i) mod k: the first request number at or after i that would map straight to id. Every key in the free heap stays >= i while request i is handled. Released keys are pushed at >= i, and each request removes the smallest key, so the rest are larger and remain >= i + 1 for the next one. Each key is also below i + k (it was pushed at some i0 <= i and is below i0 + k). So key - i is exactly the clockwise distance from i % k to the server, and the heap minimum is the server the rules ask for.
Approach
freestarts as0, 1, ..., k - 1, which are the keys for request 0.busyis a min-heap of(end time, server).- For each request
iwith arrivalaand loadl:- pop every
busyentry with end time<= aand push its server asi + (id - i) % k; - if
freeis empty, drop the request; - otherwise pop the smallest key, take server
key % k, add 1 to its count, and push(a + l, server)tobusy.
- pop every
- Return every server whose count equals the maximum.
Complexity
- Time: O(n log k), where
n = len(arrival). Every request pushes and pops each heap at most once, and both heaps hold at mostkentries - Space: O(k)
Edge Cases
- A server finishing exactly when a request arrives (
end == arrival) is free for it - All servers busy: the request is dropped and changes nothing
- Wrap-around: if every server from
i % ktok - 1is busy, the search continues from server 0. The shifted keys handle this with no special case k == 1: every key is a multiple of 1, so it reduces to "is the server free"- Ties for the most requests: return all of them, in any order
- End times reach
2 * 10^9, pastint, so Java packs(end, server)into along
Code
import heapq
class Solution:
def busiestServers(self, k: int, arrival: list[int], load: list[int]) -> list[int]:
"""
1606. Find Servers That Handled Most Number of Requests
Time: O(n log k)
Space: O(k)
"""
# A free server id is stored as the first request number >= i that maps
# to it: i + (id - i) % k. Every key stays in [i, i + k), so the minimum
# is the first free server clockwise from i % k.
free = list(range(k))
busy = [] # (end time, server)
count = [0] * k
for i, (a, l) in enumerate(zip(arrival, load)):
while busy and busy[0][0] <= a:
_, server = heapq.heappop(busy)
heapq.heappush(free, i + (server - i) % k)
if not free:
continue # every server is busy: drop the request
server = heapq.heappop(free) % k
count[server] += 1
heapq.heappush(busy, (a + l, server))
best = max(count)
return [s for s in range(k) if count[s] == best]import java.util.*;
/**
* 1606. Find Servers That Handled Most Number of Requests
* Time: O(n log k)
* Space: O(k)
*/
class Solution {
private static final int SHIFT = 17; // server ids are below 10^5 < 2^17
private static final long MASK = (1L << SHIFT) - 1;
public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
// A free server id is stored as the first request number >= i that maps
// to it: i + (id - i) mod k. Every key stays in [i, i + k), so the
// minimum is the first free server clockwise from i % k.
PriorityQueue<Integer> free = new PriorityQueue<>(k);
for (int s = 0; s < k; s++) {
free.add(s);
}
PriorityQueue<Long> busy = new PriorityQueue<>(k); // (end time, server)
int[] count = new int[k];
for (int i = 0; i < arrival.length; i++) {
long a = arrival[i];
while (!busy.isEmpty() && (busy.peek() >> SHIFT) <= a) {
int server = (int) (busy.poll() & MASK);
free.add(i + Math.floorMod(server - i, k));
}
if (free.isEmpty()) {
continue; // every server is busy: drop the request
}
int server = free.poll() % k;
count[server]++;
busy.add(((a + load[i]) << SHIFT) | server);
}
int best = 0;
for (int c : count) {
best = Math.max(best, c);
}
List<Integer> ans = new ArrayList<>();
for (int s = 0; s < k; s++) {
if (count[s] == best) {
ans.add(s);
}
}
return ans;
}
}