[Java] O(nlogk) Use TreeSet and PriorityQueue
Well, this question is really straight forward.\nMy first idea is follow the instruction listed in description and simulate.\n\nSome common skills that we can t
Well, this question is really straight forward.\nMy first idea is follow the instruction listed in description and simulate.\n\nSome common skills that we can think of:\nTo track the frequency of each server, we use an array.\nTo track the time point of each server\'s availability, we use an array to record the time point server will be free.\n\nBut if we try `i`, `i + 1`, `i + 2`, ... , it will definatly lead to TLE.\nSo, how to quickly find next empty server?\nWe can use a `TreeSet` to store the index of all free servers, then we can quickly find next free serve.\nAlso, to track which server will be free at a time point, we need to maintain a heap of busy servers.\n\n\n```java\nclass Solution {\n    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {\n        \n        int fre[] = new int[k], availability[] = new int[k], max = 0;\n        \n        TreeSet<Integer> free = new TreeSet<>();\n        PriorityQueue<Integer> busy = new PriorityQueue<>((a, b) -> availability[a] - availability[b]);\n        \n        for(int i = 0; i < k; i++) free.add(i);\n        \n        for(int i = 0; i < arrival.length; i++) {\n            // try to get all free nodes\n            while(!busy.isEmpty() && availability[busy.peek()] <= arrival[i]) {\n                free.add(busy.poll());\n            }\n            \n            if(free.isEmpty()) continue ; // drop\n            \n            \n            if(free.contains(i % k)) { // i + k server is free\n                free.remove(i % k);\n                availability[i % k] = arrival[i] + load[i];\n                busy.add(i % k);\n                \n                fre[i % k]++;\n                max = Math.max(max, fre[i % k]);\n            } else { // find next free server\n                Integer nxt = free.ceiling(i % k); // try to find a free server next to i\n                if(nxt == null) nxt = free.first(); // no free server with index larger than i. So we use a server with minimum index\n                \n                free.remove(nxt);\n                availability[nxt] = arrival[i] + load[i];\n                busy.add(nxt);\n                \n                fre[nxt]++;\n                max = Math.max(max, fre[nxt]);\n            }\n        }\n        \n        List<Integer> res = new ArrayList<>();\n        for(int i = 0; i < k; i++) if(fre[i] == max) res.add(i);\n        \n        return res;\n    }\n}\n```
[]