1606. Find Servers That Handled Most Number of Requests
Problem Overview
Request i prefers server i modulo k.
Intuition
Request i prefers server i modulo k. If that server is busy, the next free server in circular order takes the job, and if every server is busy the request is dropped. A busy min-heap stores each working server by the time it finishes. A free min-heap stores idle servers as shifted ids i plus (server minus i modulo k), so the preferred id rises to the top and wraparound to smaller ids follows from the same order. Before request i is assigned, every busy server whose end time is at most the arrival time goes back onto the free heap with a fresh shift built from the current i. When the free heap is empty the request is skipped. Otherwise the top server handles it, its count rises by one, and it returns to the busy heap with end time equal to arrival plus load. After every request, every server whose count equals the maximum count is collected into the answer.
Algorithm
- 1Push every server id onto a free min-heap with itself as the priority.
- 2For each request i, move every busy server whose end time is at most arrival[i] onto the free heap with priority i plus (server minus i modulo k).
- 3If the free heap is empty, drop the request and continue.
- 4Take the free heap top, raise its count, and push it onto the busy heap with end time arrival[i] plus load[i].
- 5Find the maximum count and return every server index that matches it.
Example Walkthrough
Input: k = 3, arrival = [1, 2, 3, 4, 5], load = [5, 2, 3, 3, 3]
- 1.Request 0 takes server 0 until time 6. Request 1 takes server 1 until time 4. Request 2 takes server 2 until time 6.
- 2.Request 3 arrives at time 4. Server 1 is free again and is preferred after the wrap from 3 modulo 3, so server 1 takes it until time 7.
- 3.Request 4 finds every remaining free choice busy or already counted toward server 1 as the unique busiest server with two requests.
Output: [1]
Common Pitfalls
- •A server that finishes at exactly the arrival time is free. Compare end time with less than or equal to arrival.
- •When the free heap is empty the request must be dropped. Do not wait for a later free server.
- •Rebuild the free heap priority from the current request index when a server is released. An old priority no longer matches the wrap order.
- •Return every server that ties the maximum count. The answer can hold more than one index.
// Approach: A busy min-heap stores (end time, server). A free min-heap stores
// server ids shifted so the next preferred id i % k comes out first, wrapping
// to smaller ids when needed. Each request frees every server whose end time
// is due, then takes the free heap top when one exists. Counts track how many
// requests each server handled, and every server that ties the maximum is kept.
// Time: O(n log k) Space: O(k)
public class Solution
{
public IList<int> BusiestServers(int k, int[] arrival, int[] load)
{
int n = arrival.Length;
int[] count = new int[k];
var free = new PriorityQueue<int, int>();
var busy = new PriorityQueue<(int end, int server), int>();
for (int s = 0; s < k; s++)
free.Enqueue(s, s);
for (int i = 0; i < n; i++)
{
int start = arrival[i];
while (busy.Count > 0 && busy.Peek().end <= start)
{
int server = busy.Dequeue().server;
int offset = i + (server - i % k + k) % k;
free.Enqueue(server, offset);
}
if (free.Count == 0)
continue;
int chosen = free.Dequeue();
count[chosen]++;
busy.Enqueue((start + load[i], chosen), start + load[i]);
}
int best = 0;
for (int s = 0; s < k; s++)
if (count[s] > best)
best = count[s];
var ans = new List<int>();
for (int s = 0; s < k; s++)
if (count[s] == best)
ans.Add(s);
return ans;
}
}