1606. 找到处理最多请求的服务器

approach 1，有序集合+优先队列

class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        TreeSet<Integer> ts = new TreeSet<>();
        // a[0] arrival a[1] k
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int n = arrival.length;
        int[] cnt = new int[k];
        int max = 0;

        for (int i = 0; i < k; i++) {
            ts.add(i);
        }

        for (int i = 0; i < n; i++) {
            while (!pq.isEmpty() && pq.peek()[0] <= arrival[i]) {
                ts.add(pq.poll()[1]);
            }
            Integer nx = ts.tailSet(i % k, true).pollFirst();
            if (nx == null) {
                if (ts.isEmpty() || (nx = ts.pollFirst()) == null) continue;
            }
            ts.remove(nx);
            load[i] += arrival[i];
            pq.offer(new int[]{load[i], nx});
            cnt[nx]++;
            if (cnt[nx] > max) {
                max = cnt[nx];
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (cnt[i] == max) ans.add(i);
        }
        return ans;
    }
}

稍微简洁一点，做题耗时仍然超过了30min...

class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        int n = arrival.length;
        int[] end = new int[n];
        int[] server = new int[n];
        int[] cnt = new int[k];
        int max = 0;
        TreeSet<Integer> tm = new TreeSet<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> end[a] - end[b]);

        for (int i = 0; i < k; i++) tm.add(i);
        for (int i = 0; i < n; i++) {
            int d = arrival[i];
            while (!pq.isEmpty() && d >= end[pq.peek()]) {
                tm.add(server[pq.poll()]);
            }
            Integer t = tm.higher(i % k - 1);
            if (t == null) t = tm.higher(-1);
            if (t == null) continue;
            cnt[t]++;
            end[i] = d + load[i];
            server[i] = t;
            tm.remove(t);
            pq.offer(i);
            if (cnt[t] > max) max = cnt[t];
        }
        
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) if (cnt[i] == max) ans.add(i);
        return ans;
    }
}