# Find Servers That Handled Most Number of Requests

This page explains Java solution to problem `Find Servers That Handled Most Number of Requests` using `TreeMap` data structure.

## Problem Statement

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:

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]

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class FindServersThatHandledMostNumberOfRequests {
public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
TreeSet<Integer> available = new TreeSet<>();
for(int server = 0; server < k; server++) available.add(server);

//[server, busyUntil order by Asc]
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] x, int[] y) {
int cmp = Integer.compare(x[1], y[1]);
if(cmp == 0) return Integer.compare(x[0], y[0]);
return cmp;
}
});

int[] count = new int[k];
int max = 0;
for(int i = 0; i < arrival.length; i++) {
int serverIndex = i % k;
int arrivalTime = arrival[i];
while(!pq.isEmpty() && pq.peek()[1] <= arrivalTime) {
}
Integer availableServer = available.ceiling(serverIndex);

//wrapping around
if(availableServer == null) availableServer = available.ceiling(0);

if(availableServer != null) {
int busyUntil = arrivalTime + load[i];
pq.offer(new int[]{availableServer, busyUntil});
available.remove(availableServer);
count[availableServer]++;
max = Math.max(max, count[availableServer]);
}
}

for(int i = 0; i < k; i++) if(count[i] == max) res.add(i);

return res;
}
}
``````

## Time Complexity

O(N * log K)) Where
N is number of request in an input array arrival
K is number of servers to handle request

## Space Complexity

O(K) Where
K is number of servers to handle request