352. Find Servers That Handled Most Number of Requests

Pop finished servers back into a sorted free set, then place each request on the first free server at or after i mod k, wrapping around if needed.

Idea

Process the requests in arrival order. At every moment a server is either free or busy until some end time. Two structures keep the simulation fast:

• A min-heap busy of (end_time, server_id) so the server that frees up soonest sits at the root.
• A sorted set free of the IDs of all currently idle servers, which we can search by value.

Walk-through (k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3])

1. Request 0 at t=1. Nothing is busy. Target server is 0 % 3 = 0, which is free, so server 0 takes it and frees at 1 + 5 = 6. free = {1, 2}.
2. Request 1 at t=2. The busy root frees at 6 > 2, so no releases. Target is 1 % 3 = 1; server 1 is free, takes it, frees at 2 + 2 = 4. free = {2}.
3. Request 2 at t=3. Target is 2 % 3 = 2; server 2 is free, takes it, frees at 3 + 3 = 6. free = {} — all busy.
4. Request 3 at t=4. The busy root is server 1 (frees at 4 ≤ 4), so release it: free = {1}. Target is 3 % 3 = 0. No free ID is ≥ 0 that we want? The smallest free ID at or after 0 is 1, so server 1 takes it and frees at 4 + 3 = 7. Its count is now 2.
5. Request 4 at t=5. The busy root frees at 6 > 5, nothing releases, free is empty, so the request is dropped.

Counts end at [1, 2, 1], so the busiest server is 1.

Placing a request

To honor "start at i % k and wrap around," search the sorted free set for the smallest ID >= i % k. If one exists, use it; otherwise wrap and use the smallest free ID overall. When a server is chosen, remove it from free and push (arrival[i] + load[i], server) onto busy.

Finding the answer

Track a count per server. After all requests, the busiest servers are every ID whose count equals the maximum.

Complexity

• Time: O((n + k) log k) — each server enters and leaves the heap and the ordered set O(1) times, each operation costing O(log k).
• Space: O(n + k) for the heap, the free set, and the counts.

import java.util.*;

class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        TreeSet<Integer> free = new TreeSet<>();
        for (int i = 0; i < k; i++) free.add(i);
        // busy: (endTime, server), earliest-freeing at the root.
        PriorityQueue<long[]> busy = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        int[] count = new int[k];

        for (int i = 0; i < arrival.length; i++) {
            long t = arrival[i];
            // Release every server that has finished by this arrival time.
            while (!busy.isEmpty() && busy.peek()[0] <= t) {
                free.add((int) busy.poll()[1]);
            }
            if (free.isEmpty()) continue;  // all busy -> dropped

            Integer s = free.ceiling(i % k);
            if (s == null) s = free.first();  // wrap around to the smallest free ID
            free.remove(s);

            count[s]++;
            busy.offer(new long[]{t + load[i], s});
        }

        int best = 0;
        for (int c : count) best = Math.max(best, c);
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) if (count[i] == best) res.add(i);
        return res;
    }
}