# Find Servers That Handled Most Number of Requests
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests)
Canonical: https://scaleengineer.com/dsa/problems/find-servers-that-handled-most-number-of-requests
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue), Ordered Set
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one), [Citadel](https://scaleengineer.com/companies/citadel), [Wish](https://scaleengineer.com/companies/wish)
---
## Problem
You have `k` servers numbered from `0` to `k-1` that are being used to handle multiple requests simultaneously. Each server has infinite computational capacity but **cannot handle more than one request at a time**. The requests are assigned to servers according to a specific algorithm:

* The `ith` (0-indexed) request arrives.
* If all servers are busy, the request is dropped (not handled at all).
* If the `(i % k)th` server is available, assign the request to that server.
* Otherwise, assign the request to the next available server (wrapping around the list of servers and starting from 0 if necessary). For example, if the `ith` server is busy, try to assign the request to the `(i+1)th` server, then the `(i+2)th` server, and so on.

You are given a **strictly increasing** array `arrival` of positive integers, where `arrival[i]` represents the arrival time of the `ith` request, and another array `load`, where `load[i]` represents the load of the `ith` request (the time it takes to complete). Your goal is to find the **busiest server(s)**. A server is considered **busiest** if it handled the most number of requests successfully among all the servers.

Return _a list containing the IDs (0-indexed) of the **busiest server(s)**_. You may return the IDs in any order.

**Example 1:**

![](https://assets.glich.co/dsa/find-servers-that-handled-most-number-of-requests/image0.png) 

**Input:** k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] 
**Output:** [1] 
**Explanation:** 
All of the servers start out available.
The first 3 requests are handled by the first 3 servers in order.
Request 3 comes in. Server 0 is busy, so it's assigned to the next available server, which is 1.
Request 4 comes in. It cannot be handled since all servers are busy, so it is dropped.
Servers 0 and 2 handled one request each, while server 1 handled two requests. Hence server 1 is the busiest server.

**Example 2:**

**Input:** k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
**Output:** [0]
**Explanation:** 
The first 3 requests are handled by first 3 servers.
Request 3 comes in. It is handled by server 0 since the server is available.
Server 0 handled two requests, while servers 1 and 2 handled one request each. Hence server 0 is the busiest server.

**Example 3:**

**Input:** k = 3, arrival = [1,2,3], load = [10,12,11]
**Output:** [0,1,2]
**Explanation:** Each server handles a single request, so they are all considered the busiest.

**Constraints:**

* `1 <= k <= 105`
* `1 <= arrival.length, load.length <= 105`
* `arrival.length == load.length`
* `1 <= arrival[i], load[i] <= 109`
* `arrival` is **strictly increasing**.

# Approaches
## Brute-force Simulation
This approach directly simulates the server assignment process as described in the problem. For each incoming request, it performs a linear scan through the servers to find an available one, following the specified wrap-around logic. While simple to conceptualize, its performance degrades significantly as the number of servers increases.
**Time:** O(N * K), where `N` is the number of requests and `K` is the number of servers. For each of the `N` requests, we might scan up to `K` servers. · **Space:** O(K) to store `requestCounts` and `finishTimes`.
**Pros:** Easy to understand and implement.; Low memory overhead compared to more complex solutions.
**Cons:** Time complexity is too high for the given constraints, likely resulting in a 'Time Limit Exceeded' error.
### Explanation
We maintain two arrays of size `k`: `requestCounts` to track the number of requests handled by each server, and `finishTimes` to store the time each server becomes free. We iterate through each request. For the `i`-th request arriving at `arrival[i]`, we check servers starting from `i % k`, then `(i+1) % k`, and so on, wrapping around. The first server `j` we find whose `finishTimes[j]` is less than or equal to `arrival[i]` is assigned the request. We then update `finishTimes[j]` to `arrival[i] + load[i]` and increment `requestCounts[j]`. If the entire loop over `k` servers completes without finding an available one, the request is dropped. After processing all requests, we find the maximum value in `requestCounts` and return the indices of all servers that achieved this count.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        int[] requestCounts = new int[k];
        long[] finishTimes = new long[k];

        for (int i = 0; i < arrival.length; i++) {
            long currentTime = arrival[i];
            int preferredServer = i % k;
            int serverToUse = -1;

            for (int j = 0; j < k; j++) {
                int serverIndex = (preferredServer + j) % k;
                if (finishTimes[serverIndex] <= currentTime) {
                    serverToUse = serverIndex;
                    break;
                }
            }

            if (serverToUse != -1) {
                finishTimes[serverToUse] = currentTime + load[i];
                requestCounts[serverToUse]++;
            }
        }

        int maxRequests = 0;
        for (int count : requestCounts) {
            maxRequests = Math.max(maxRequests, count);
        }

        List<Integer> busiest = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (requestCounts[i] == maxRequests) {
                busiest.add(i);
            }
        }

        return busiest;
    }
}
```
### Algorithm
- 1. Initialize `requestCounts` and `finishTimes` arrays of size `k` with zeros.
- 2. For each request `i` from `0` to `n-1`:
    - a. Iterate through potential servers `j` from `0` to `k-1`.
    - b. Calculate the server index to check: `serverIdx = (i + j) % k`.
    - c. If `finishTimes[serverIdx] <= arrival[i]`, the server is available.
    - d. Assign the request: update `finishTimes[serverIdx]`, increment `requestCounts[serverIdx]`, and break the inner loop to proceed to the next request.
- 3. After the main loop, find the maximum value in `requestCounts`.
- 4. Return a list of all server indices whose count matches the maximum.

## Optimized Simulation with Priority Queue and TreeSet
This approach significantly improves the efficiency of the simulation by using appropriate data structures. A min-priority queue is used to manage busy servers, and a `TreeSet` (a balanced binary search tree) is used to manage available servers. This combination allows for fast updates of server availability and efficient searching for the next server to assign a request to.
**Time:** O(N * log K). Each of the `N` requests involves a few operations (add, remove, poll, ceiling) on the `TreeSet` and `PriorityQueue`, which have a size of at most `K`. Each operation takes `O(log K)` time. · **Space:** O(K). The `TreeSet` and `PriorityQueue` can store up to `K` elements.
**Pros:** Highly efficient and passes the given constraints.; Scales well with a large number of servers and requests.
**Cons:** More complex to implement due to the use of advanced data structures.; Slightly higher constant factor in time and space complexity compared to the naive approach, though asymptotically superior.
### Explanation
We maintain a count of requests for each server in an array. To manage server states, we use two main data structures: a min-priority queue `busyServers` that stores `[finishTime, serverId]` pairs, ordered by `finishTime`, and a `TreeSet` `availableServers` that stores the IDs of available servers. Initially, all servers are in `availableServers`. For each request `i` arriving at `currentTime`, we first update our set of available servers by polling from `busyServers` all servers whose `finishTime` is less than or equal to `currentTime` and adding them back to `availableServers`. If `availableServers` is empty, the request is dropped. Otherwise, we find the appropriate server using the `TreeSet`. We search for the smallest server ID greater than or equal to `i % k` using `availableServers.ceiling(i % k)`. If such a server doesn't exist (i.e., `ceiling` returns null), we wrap around and take the smallest available server ID, given by `availableServers.first()`. The chosen server is then removed from `availableServers`, its request count is incremented, and it's added to `busyServers` with its new finish time. Finally, we identify and return the busiest servers based on the counts.

```java
import java.util.*;

class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        int[] requestCounts = new int[k];
        
        PriorityQueue<long[]> busyServers = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        TreeSet<Integer> availableServers = new TreeSet<>();
        for (int i = 0; i < k; i++) {
            availableServers.add(i);
        }

        for (int i = 0; i < arrival.length; i++) {
            long currentTime = arrival[i];

            while (!busyServers.isEmpty() && busyServers.peek()[0] <= currentTime) {
                long[] finishedServer = busyServers.poll();
                availableServers.add((int) finishedServer[1]);
            }

            if (availableServers.isEmpty()) {
                continue;
            }

            int targetServer = i % k;
            Integer serverId = availableServers.ceiling(targetServer);
            
            if (serverId == null) {
                serverId = availableServers.first();
            }

            availableServers.remove(serverId);
            requestCounts[serverId]++;
            long finishTime = currentTime + load[i];
            busyServers.add(new long[]{finishTime, (long)serverId});
        }

        int maxRequests = 0;
        for (int count : requestCounts) {
            maxRequests = Math.max(maxRequests, count);
        }

        List<Integer> busiest = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (requestCounts[i] == maxRequests) {
                busiest.add(i);
            }
        }

        return busiest;
    }
}
```
### Algorithm
- 1. Initialize `requestCounts` array of size `k` with zeros.
- 2. Create a `TreeSet` `availableServers` and populate it with server IDs from `0` to `k-1`.
- 3. Create a min-priority queue `busyServers` to store `[finishTime, serverId]` pairs.
- 4. For each request `i` from `0` to `n-1`:
    - a. Let `currentTime = arrival[i]`.
    - b. Free up finished servers: move servers from `busyServers` to `availableServers` if their finish time is `<= currentTime`.
    - c. If `availableServers` is empty, drop the request and continue.
    - d. Determine the target server: find `server_id = availableServers.ceiling(i % k)`. If it's null, use `availableServers.first()`.
    - e. Assign the request: remove `server_id` from `availableServers`, increment its count, and add `[currentTime + load[i], server_id]` to `busyServers`.
- 5. After the loop, find the maximum value in `requestCounts`.
- 6. Return a list of all server indices whose count matches the maximum.

# Solutions
### Java

```java
class Solution { public List < Integer > busiestServers ( int k , int [] arrival , int [] load ) { int [] cnt = new int [ k ]; PriorityQueue < int []> busy = new PriorityQueue <>( Comparator . comparingInt ( a -> a [ 0 ])); TreeSet < Integer > free = new TreeSet <>(); for ( int i = 0 ; i < k ; ++ i ) { free . add ( i ); } for ( int i = 0 ; i < arrival . length ; ++ i ) { int start = arrival [ i ]; int end = start + load [ i ]; while (! busy . isEmpty () && busy . peek ()[ 0 ] <= start ) { free . add ( busy . poll ()[ 1 ]); } if ( free . isEmpty ()) { continue ; } Integer server = free . ceiling ( i % k ); if ( server == null ) { server = free . first (); } ++ cnt [ server ]; busy . offer ( new int [] { end , server }); free . remove ( server ); } int mx = 0 ; for ( int v : cnt ) { mx = Math . max ( mx , v ); } List < Integer > ans = new ArrayList <>(); for ( int i = 0 ; i < k ; ++ i ) { if ( cnt [ i ] == mx ) { ans . add ( i ); } } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < int > busiestServers ( int k , vector < int >& arrival , vector < int >& load ) { set < int > free ; for ( int i = 0 ; i < k ; ++ i ) free . insert ( i ); priority_queue < pair < int , int > , vector < pair < int , int >> , greater <>> busy ; vector < int > cnt ( k ); for ( int i = 0 ; i < arrival . size (); ++ i ) { int start = arrival [ i ], end = start + load [ i ]; while ( ! busy . empty () && busy . top (). first <= start ) { free . insert ( busy . top (). second ); busy . pop (); } if ( free . empty ()) continue ; auto p = free . lower_bound ( i % k ); if ( p == free . end ()) p = free . begin (); int server = * p ; ++ cnt [ server ]; busy . emplace ( end , server ); free . erase ( server ); } int mx = * max_element ( cnt . begin (), cnt . end ()); vector < int > ans ; for ( int i = 0 ; i < k ; ++ i ) if ( cnt [ i ] == mx ) ans . push_back ( i ); return ans ; } };
```

### Python

```python
from sortedcontainers import SortedList class Solution : def busiestServers ( self , k : int , arrival : List [ int ], load : List [ int ]) -> List [ int ]: free = SortedList ( range ( k )) busy = [] cnt = [ 0 ] * k for i , ( start , t ) in enumerate ( zip ( arrival , load )): while busy and busy [ 0 ][ 0 ] <= start : free . add ( busy [ 0 ][ 1 ]) heappop ( busy ) if not free : continue j = free . bisect_left ( i % k ) if j == len ( free ): j = 0 server = free [ j ] cnt [ server ] += 1 heappush ( busy , ( start + t , server )) free . remove ( server ) mx = max ( cnt ) return [ i for i , v in enumerate ( cnt ) if v == mx ]
```