1882. 使用服务器处理任务Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你两个下标从 0 开始的整数数组 servers 和 tasks ，长度分别为 n 和 m 。servers[i] 是第 i 台服务器的权重，而 tasks[j] 是处理第 j 项任务所需要的时间（单位：秒）。

你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j 秒可以开始处理。处理第 j 项任务时，你需要为它分配一台权重最小的空闲服务器。如果存在多台相同权重的空闲服务器，请选择下标最小的服务器。如果一台空闲服务器在第 t 秒分配到第 j 项任务，那么在 t + tasks[j] 时它将恢复空闲状态。

如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并尽可能早地处理剩余任务。如果有多项任务等待分配，则按照下标递增的顺序完成分配。

如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。

构建长度为 m 的答案数组 ans ，其中 ans[j] 是第 j 项任务分配的服务器的下标。

返回答案数组 ans 。

示例 1：

输入：servers = [3,3,2], tasks = [1,2,3,2,1,2]
输出：[2,2,0,2,1,2]
解释：事件按时间顺序如下：
- 0 秒时，第 0 项任务加入到任务队列，使用第 2 台服务器处理到 1 秒。
- 1 秒时，第 2 台服务器空闲，第 1 项任务加入到任务队列，使用第 2 台服务器处理到 3 秒。
- 2 秒时，第 2 项任务加入到任务队列，使用第 0 台服务器处理到 5 秒。
- 3 秒时，第 2 台服务器空闲，第 3 项任务加入到任务队列，使用第 2 台服务器处理到 5 秒。
- 4 秒时，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 5 秒。
- 5 秒时，所有服务器都空闲，第 5 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。

示例 2：

输入：servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
输出：[1,4,1,4,1,3,2]
解释：事件按时间顺序如下：
- 0 秒时，第 0 项任务加入到任务队列，使用第 1 台服务器处理到 2 秒。
- 1 秒时，第 1 项任务加入到任务队列，使用第 4 台服务器处理到 2 秒。
- 2 秒时，第 1 台和第 4 台服务器空闲，第 2 项任务加入到任务队列，使用第 1 台服务器处理到 4 秒。
- 3 秒时，第 3 项任务加入到任务队列，使用第 4 台服务器处理到 7 秒。
- 4 秒时，第 1 台服务器空闲，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 9 秒。
- 5 秒时，第 5 项任务加入到任务队列，使用第 3 台服务器处理到 7 秒。
- 6 秒时，第 6 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。

提示：

servers.length == n
tasks.length == m
1 <= n, m <= 2 * 10⁵
1 <= servers[i], tasks[j] <= 2 * 10⁵

# 思路

PriorityQueue

# 解法

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> (o1[0] - o2[0] == 0 ? o1[1] - o2[1] : o1[0] - o2[0]));
        for (int i = 0; i < servers.length; i++) {
            pq.offer(new int[]{servers[i], i});
        }
        
        int[] ans = new int[tasks.length];
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();
        int curTime = 0;
        for (int i = 0; i < tasks.length; ) {
            while (!map.isEmpty() && map.firstKey() <= curTime) {
                int t = map.firstKey();
                List<int[]> tmp = map.get(t);
                for (int[] x : tmp) {
                    pq.offer(x);
                }
                map.remove(t);
            }
            // 如果有空闲服务器，把当前任务分配给服务器
            if (!pq.isEmpty()) {
                int[] tmp = pq.poll();
                ans[i] = tmp[1];
                int finishTime = curTime + tasks[i];
                if (!map.containsKey(finishTime)) {
                    map.put(finishTime, new ArrayList<int[]>());
                }
                map.get(finishTime).add(tmp);
                i++;
                curTime = Math.max(curTime, i);
            } 
            // 没有空闲服务器，要等到空闲时间
            else {
                curTime = map.firstKey();
            }
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# 总结

分析出几种情况，然后分别对各个情况实现

#Java