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.

&nbsp;
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]
Explanation: Each server handles a single request, so they are all considered the busiest.


&nbsp;
Constraints:


	1 &lt;= k &lt;= 105
	1 &lt;= arrival.length, load.length &lt;= 105
	arrival.length == load.length
	1 &lt;= arrival[i], load[i] &lt;= 109
	arrival is strictly increasing.


class Solution:
    def busiestServers(self, k: int, A: List[int], B: List[int]) -> List[int]:
        available = list(range(k)) # already a min-heap
        busy = [] 
        res = [0] * k
        for i, a in enumerate(A):
            while busy and busy[0][0] <= a: # these are done, put them back as available
                _, x = heapq.heappop(busy)
                heapq.heappush(available, i + (x-i)%k) # invariant: min(available) is at least i, at most i+k-1
            if available: 
                j = heapq.heappop(available) % k
                heapq.heappush(busy, (a+B[i],j))
                res[j] += 1
        a = max(res)
        return [i for i in range(k) if res[i] == a]
class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {

        // use a tree to track available servers
        TreeSet<Integer> availableServerIdxs = new TreeSet<Integer>();
        for (int num = 0; num < k; num++) {
            availableServerIdxs.add(num);
        }
        // use a PQ to maintain the availability based on curTime + loadTime and the server index = idx%k
        Queue<int[]> runningServers = new PriorityQueue<>((a, b)->(a[0] - b[0]));

        int[] serverHandledReqCount = new int[k];

        for (int idx = 0; idx < arrival.length; idx++) {
            int newTaskCompletionTime = arrival[idx];

          // peek if the server's work time is less than or equal to the next task completion time, if it is poll those servers from the running servers queue and add the index of that server to the availableServerIdxs treeSet
            while (!runningServers.isEmpty() && runningServers.peek()[0] <= newTaskCompletionTime) {
                int freedServer = runningServers.poll()[1];
                availableServerIdxs.add(freedServer);
            }

            if (availableServerIdxs.size() == 0) continue; // all busy

            // to always get the last freed server
            Integer serverIdx = availableServerIdxs.ceiling(idx % k);

            if (serverIdx == null) {
                serverIdx = availableServerIdxs.first();
            }

            serverHandledReqCount[serverIdx]++;
            availableServerIdxs.remove(serverIdx);

            runningServers.offer(new int[] {newTaskCompletionTime + load[idx], serverIdx});
        }

        int max = Arrays.stream(serverHandledReqCount).max().getAsInt();
        return IntStream.range(0, k).filter(i -> serverHandledReqCount[i] == max).boxed().collect(Collectors.toList());

        //return findMaxesInCounter(counter);
    }

    /*
    private List<Integer> findMaxesInCounter(int[] counter) {
        int max = 0;
        for (int i = 0; i < counter.length; i++) {
            max = Math.max(max, counter[i]);
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < counter.length; i++) {
            if (counter[i] == max) {
                result.add(i);
            }
        }
        return result;
    }
    */
}
class Solution {
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
        int n = (int)arrival.size();
        
        set<int> freeServers;
        for (int i = 0; i < k; i++) freeServers.insert(i);
        
        vector<int> serverTaskCount(k, 0);
        
        set<pair<int, int>> workingServers;     // [end time, server index]
        for (int i = 0; i < n; i++) {
            int startTime = arrival[i];
            
            while (!workingServers.empty() && workingServers.begin()->first <= startTime) {
                auto s = *workingServers.begin();
                workingServers.erase(workingServers.begin());
                freeServers.insert(s.second);
            }
            
            if (freeServers.empty()) continue;
            
            int serverIndex = -1;
            auto it = freeServers.lower_bound(i % k);
            if (it == freeServers.end()) {
                serverIndex = *freeServers.begin();
                freeServers.erase(freeServers.begin());
            } else {
                serverIndex = *it;
                freeServers.erase(it);
            }
            
            workingServers.insert({startTime + load[i], serverIndex});
            
            serverTaskCount[serverIndex]++;
            //printf("Task %d (%d, %d) assigned to server %d\n", i, startTime, load[i], serverIndex);
        }
        // for (auto x : serverTaskCount) cout << x << " ";
        // cout << endl;
        
        vector<int> ret;
        int maxVal = *max_element(serverTaskCount.begin(), serverTaskCount.end());
        for (int i = 0; i < k; i++) 
            if (maxVal == serverTaskCount[i]) ret.push_back(i);
        
        return ret;
    }
};
var busiestServers = function(k, arrival, load) {
    let loadMap = {};
    let pq = new MinPriorityQueue({ compare: (a,b) => a[1] - b[1] });
    let availableServers = new Set(new Array(k).fill(0).map((_, index) => index));

    for (let i = 0; i < arrival.length; i++) {
        // calc end time
        let end = arrival[i] + load[i];
        
        // bring server back
        while (pq.front()?.[1] <= arrival[i]) {
            const [server] = pq.dequeue();
            availableServers.add(server);
        }
        
        let server = i % k;
        // drop if no available server
        if (availableServers.size === 0) continue;
        
        // find the next avaiable sever
        while (!availableServers.has(server)) {
            server++;
            if (server === k + 1) {
                server = 0;
            }
        }
        
        // record the load
        if (!loadMap[server]) {
            loadMap[server] = 0;
        }
        
        loadMap[server]++;
        
        availableServers.delete(server);
        pq.enqueue([server, end]);
    }
    
    let res = [];
    let sorted = Object.entries(loadMap).sort((a,b) => b[1] - a[1]);
    let max = sorted[0][1];
    let i = 0;
    while (sorted[i]?.[1] === max) {
        res.push(+sorted[i++][0]);
    }
    
    return res;
};
Find Servers That Handled Most Number of Requests