题目描述
给你两个 下标从 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 == ntasks.length == m1 <= n, m <= 2 * 1051 <= servers[i], tasks[j] <= 2 * 105
解法
方法一：优先队列（小根堆）
我们用一个小根堆 \(\textit{idle}\) 来维护所有的空闲服务器，其中每个元素是一个二元组 \((x, i)\)，表示第 \(i\) 台服务器的权重为 \(x\)。用一个小根堆 \(\textit{busy}\) 来维护所有的忙碌服务器，其中每个元素是一个三元组 \((w, s, i)\)，表示第 \(i\) 台服务器在第 \(w\) 秒恢复空闲，权重为 \(s\)。初始时我们将所有的服务器加入到 \(\textit{idle}\) 中。
接下来，我们遍历所有的任务，对于第 \(j\) 项任务，我们首先将所有在第 \(j\) 秒或之前恢复空闲的服务器从 \(\textit{busy}\) 中移除，添加到 \(\textit{idle}\) 中。然后我们从 \(\textit{idle}\) 中取出一个权重最小的服务器，将其加入到 \(\textit{busy}\) 中，处理第 \(j\) 项任务。如果 \(\textit{idle}\) 为空，我们从 \(\textit{busy}\) 中取出一个恢复时间最早的服务器，将其加入到 \(\textit{busy}\) 中，处理第 \(j\) 项任务。
遍历结束后，我们得到了答案数组 \(\textit{ans}\)。
时间复杂度 \(O((n + m) \log n)\)，其中 \(n\) 为服务器的数量，\(m\) 为任务的数量。空间复杂度 \(O(n)\)。其中 \(n\) 和 \(m\) 分别为服务器和任务的数量。
相似题目：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
idle = [(x, i) for i, x in enumerate(servers)]
heapify(idle)
busy = []
ans = []
for j, t in enumerate(tasks):
while busy and busy[0][0] <= j:
_, s, i = heappop(busy)
heappush(idle, (s, i))
if idle:
s, i = heappop(idle)
heappush(busy, (j + t, s, i))
else:
w, s, i = heappop(busy)
heappush(busy, (w + t, s, i))
ans.append(i)
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
41
42
43 | class Solution {
public int[] assignTasks(int[] servers, int[] tasks) {
int n = servers.length;
PriorityQueue<int[]> idle = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
}
return a[1] - b[1];
});
PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0];
}
if (a[1] != b[1]) {
return a[1] - b[1];
}
return a[2] - b[2];
});
for (int i = 0; i < n; i++) {
idle.offer(new int[] {servers[i], i});
}
int m = tasks.length;
int[] ans = new int[m];
for (int j = 0; j < m; ++j) {
int t = tasks[j];
while (!busy.isEmpty() && busy.peek()[0] <= j) {
int[] p = busy.poll();
idle.offer(new int[] {p[1], p[2]});
}
if (!idle.isEmpty()) {
int i = idle.poll()[1];
ans[j] = i;
busy.offer(new int[] {j + t, servers[i], i});
} else {
int[] p = busy.poll();
int i = p[2];
ans[j] = i;
busy.offer(new int[] {p[0] + t, p[1], i});
}
}
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 | class Solution {
public:
vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
using pii = pair<int, int>;
using arr3 = array<int, 3>;
priority_queue<pii, vector<pii>, greater<pii>> idle;
priority_queue<arr3, vector<arr3>, greater<arr3>> busy;
for (int i = 0; i < servers.size(); ++i) {
idle.push({servers[i], i});
}
int m = tasks.size();
vector<int> ans(m);
for (int j = 0; j < m; ++j) {
int t = tasks[j];
while (!busy.empty() && busy.top()[0] <= j) {
auto [_, s, i] = busy.top();
busy.pop();
idle.push({s, i});
}
if (!idle.empty()) {
auto [s, i] = idle.top();
idle.pop();
ans[j] = i;
busy.push({j + t, s, i});
} else {
auto [w, s, i] = busy.top();
busy.pop();
ans[j] = i;
busy.push({w + t, s, i});
}
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 | func assignTasks(servers []int, tasks []int) (ans []int) {
idle := hp{}
busy := hp2{}
for i, x := range servers {
heap.Push(&idle, pair{x, i})
}
for j, t := range tasks {
for len(busy) > 0 && busy[0].w <= j {
p := heap.Pop(&busy).(tuple)
heap.Push(&idle, pair{p.s, p.i})
}
if idle.Len() > 0 {
p := heap.Pop(&idle).(pair)
ans = append(ans, p.i)
heap.Push(&busy, tuple{j + t, p.s, p.i})
} else {
p := heap.Pop(&busy).(tuple)
ans = append(ans, p.i)
heap.Push(&busy, tuple{p.w + t, p.s, p.i})
}
}
return
}
type pair struct {
s int
i int
}
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool {
a, b := h[i], h[j]
return a.s < b.s || a.s == b.s && a.i < b.i
}
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
type tuple struct {
w int
s int
i int
}
type hp2 []tuple
func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool {
a, b := h[i], h[j]
return a.w < b.w || a.w == b.w && (a.s < b.s || a.s == b.s && a.i < b.i)
}
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any) { *h = append(*h, v.(tuple)) }
func (h *hp2) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
|
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 | function assignTasks(servers: number[], tasks: number[]): number[] {
const idle = new PriorityQueue({
compare: (a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]),
});
const busy = new PriorityQueue({
compare: (a, b) =>
a[0] === b[0] ? (a[1] === b[1] ? a[2] - b[2] : a[1] - b[1]) : a[0] - b[0],
});
for (let i = 0; i < servers.length; ++i) {
idle.enqueue([servers[i], i]);
}
const ans: number[] = [];
for (let j = 0; j < tasks.length; ++j) {
const t = tasks[j];
while (busy.size() > 0 && busy.front()![0] <= j) {
const [_, s, i] = busy.dequeue()!;
idle.enqueue([s, i]);
}
if (idle.size() > 0) {
const [s, i] = idle.dequeue()!;
busy.enqueue([j + t, s, i]);
ans.push(i);
} else {
const [w, s, i] = busy.dequeue()!;
busy.enqueue([w + t, s, i]);
ans.push(i);
}
}
return ans;
}
|