力扣AC：找到处理请求最多的服务器 - 困难

题目链接

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

题目描述

实现代码

实现思路：首先，我们要确定需要保存的信息：

1. 空闲服务器列表；
2. 作业服务器的作业完成时间；
3. 所有服务器已接收任务数量；
4. 当前接收的最多的任务数量；

然后，我们思考两个点：

1. 如何记录作业服务器的作业完成时间；
2. 如何使服务器成环；

问题1：由题意可知，作业i的完成时间可以记为：arr[i] + load[i] = j，即在j以及j之后的作业都可以在i位置处进行接纳；

问题2：对服务器依然进行普通数组遍历，在遍历完成后，对数组进行从0开始遍历；遍历两次即可；

实现代码：

class Solution {
    static int N = 100010;
    static int[] cnts = new int[N];
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        Arrays.fill(cnts, 0);
        int n = arrival.length, max = 0;
        /**
         * 使用优先队列来存储每一个作业任务，按照结束时间进行升序；
         * 这样当一个新的任务进来，只需要跟第一个服务器结束时间进行比较就能知道是否有空闲服务器了
         */
        PriorityQueue<int[]> busy = new PriorityQueue<>((a,b)->a[1]-b[1]);
        /**
         * 使用有序Set存储空闲服务器序列，便于后面ceiling查找
         */
        TreeSet<Integer> free = new TreeSet<>();
        for (int i = 0; i < k; i++) free.add(i);
        for (int i = 0; i < n; i++) {
            int start = arrival[i], end = start + load[i];
            while (!busy.isEmpty() && busy.peek()[1] <= start) free.add(busy.poll()[0]);
            // TreeSet.ceiling(n)返回当前Set中大于或等于n的最小元素
            Integer u = free.ceiling(i % k);
            // 成环
            if (u == null) u = free.ceiling(0);
            if (u == null) continue;
            free.remove(u);
            busy.add(new int[]{u, end});
            max = Math.max(max, ++cnts[u]);
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (cnts[i] == max) ans.add(i);
        }
        return ans;
    }
}