LeetCode 第 243 场周赛

#1882 Process Tasks Using Servers

Posted by MatthewHan on 2021-06-07

Problem Description

  • 给你两个下标从 0 开始的整数数组 serverstasks ,长度分别为 nmservers[i] 是第 i 台服务器的权重 ,而 tasks[j]是处理第 j 项任务所需要的时间(单位:秒)。

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

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

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

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

  • 返回答案数组 ans

note

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

e.g.

  • 示例 1:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    输入: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:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    输入: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 秒。

Solution

第 243 场周赛的第三题,虽然这场没参加(周赛基本都起不来),不过后来做了下还挺有趣,TLE 了一发,感觉很适合拿来面试的考察求职者的代码设计以及优化能力。主要考察堆排序、队列、多任务处理这些点。

甚至我都快想要开多个线程来做了。

这题可以直接模拟,模拟法需要注意的三个地方吧,不然会超时:

  1. 注意存在某个时刻会出现多个任务可被执行
  2. 防止 TLE :直接跳转到运行队列中的最先空闲下来的服务器时间节点
  3. 防止 TLE :两个优先队列处理(运行态和就绪态)
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public int[] assignTasks(int[] servers, int[] tasks) {
int[] ans = new int[tasks.length];
// 运行态
// 运行中的服务器, 之前这里是 Queue, 没有及时 break, 所以拉了
// int[]: 长度为 2, 第 1 位是 serverId, 第 2 位是当前时间 + task 需要执行的时长
PriorityQueue<int[]> runtimeServerQueue = new PriorityQueue<>((o1, o2) -> {
return Integer.compare(o1[1], o2[1]);
});
// 就绪态
// 等待被分配的服务器
// int[]: 长度为 2, 第 1 位是 serverId, 第 2 位是服务器权重
PriorityQueue<int[]> pendingServerQueue = new PriorityQueue<>((o1, o2) -> {
// 先判权重升序, 权重一样, 则按照下标升序
if (o1[1] == o2[1]) {
return Integer.compare(o1[0], o2[0]);
} else {
return Integer.compare(o1[1], o2[1]);
}
});
// 先将所有的服务器塞到等待队列中
for (int i = 0; i < servers.length; i++) {
pendingServerQueue.offer(new int[]{i, servers[i]});
}
// 每秒需要被执行的任务
Queue<Integer> taskQueue = new LinkedList<>();
for (int t : tasks) {
taskQueue.offer(t);
}
int sec = 0;
int trueSec = 0;
while (!taskQueue.isEmpty()) {
int b = 0x3f3f3f3f;
// step0. 先处理在运行的 serverQueue
int limit = runtimeServerQueue.size();
for (int i = 0; i < limit; i++) {
int[] task = runtimeServerQueue.poll();
// 根据当前和当前储存的预期完成时间比较, 一致则说明任务完成
if (task[1] == trueSec) {
// 加入到等待队列
pendingServerQueue.offer(new int[]{task[0], servers[task[0]]});
} else {
// b: 运行中的服务器中最先会空闲的预期时间
b = Math.min(b, task[1]);
runtimeServerQueue.offer(task);
// 因为是优先队列, 一旦 else 了, Queue 后面服务器都不可能是这个时间节点完成
// 所以这里可以 break, 不然会 TLE
break;
}
}
// step1. 选择 空闲 / 权重最小 / 下标最小 的服务器
// 存在空闲服务器
if (!pendingServerQueue.isEmpty()) {
// 因为可能轮转了很多轮, 所以 taskQueue 里面的很多任务都可以在当前时间执行了(可能会有多个任务可执行)
while (sec < trueSec && !taskQueue.isEmpty() && !pendingServerQueue.isEmpty()) {
int task = taskQueue.poll();
int[] runnableServer = pendingServerQueue.poll();
ans[sec++] = runnableServer[0];
// 将 空闲的服务器 加入到 运行的服务器队列 中
runtimeServerQueue.offer(new int[]{runnableServer[0], trueSec + task});
}
trueSec++;
} else {
// 防止 TLE 关键, 跳转到 runtime 服务器最先空闲的时间节点
trueSec = b;
}
}
return ans;
}
}