# 1606. Find Servers That Handled Most Number of Requests
###### tags: `Leetcode` `Hard` `TreeMap` `Priority Queue`
Link: https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/
## 思路 $O(NlogN)$ $O(N)$
用treeset记录当前available的server
用priority queue记录当前work中的server
## Code

class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        TreeSet<Integer> available = new TreeSet<>();
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        int[] counter = new int[k];
        int busiest = 0;
        //Initially, all servers are available
        for(int i=0; i<k; i++){
            available.add(i);
        }
        for(int i=0; i<arrival.length; i++){
            int curTime = arrival[i];
            int endTime = arrival[i]+load[i];
            //find all available servers until now
            while(!pq.isEmpty() && pq.peek()[0]<=curTime){
                available.add(pq.poll()[1]);
            }
            
            if(available.isEmpty()) continue;
            //find which server to assign next
            Integer nextServer = available.ceiling(i%k);
            if(nextServer == null) nextServer = available.first();
            available.remove(nextServer);
            counter[nextServer]++;
            busiest = Math.max(busiest, counter[nextServer]);
            pq.add(new int[]{endTime, nextServer});
        }
        //find server with task nums equal to busiest
        List<Integer> ans = new ArrayList<>();
        for(int i=0; i<counter.length; i++){
            if(counter[i]==busiest) ans.add(i);
        }
        return ans;
    }
}