1882-使用服务器处理任务

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你两个 下标从 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 * 105
  • 1 <= servers[i], tasks[j] <= 2 * 105

方法一：优先队列

思路与算法

我们使用两个优先队列分别存储工作中的服务器以及空闲的服务器：

  • 优先队列 busy 存储工作中的服务器，每一台服务器用二元组 (t, \textit{idx}) 表示，其中 t 为该服务器结束工作的时间，idx 为该服务器的编号。优先队列的队首服务器满足 t 最小，并且在 t 相同的情况下，idx 最小。

  • 优先队列 idle 存储空闲的服务器，每一台服务器用二元组 (w, \textit{idx}) 表示，其中 w 为该服务器的 weight，idx 为该服务器的编号。优先队列的队首服务器满足 w 最小，并且在 w 相同的情况下，idx 最小。

这样设计的好处在于：

  • 随着时间的增加，我们可以依次从优先队列 busy 中取出已经工作完成（即时间大于等于 t）的服务器；

  • 当我们需要给任务安排服务器时，我们可以依次从优先队列 idle 中取出可用的服务器。

因此，我们就可以设计出算法的流程：

  • 在初始时，我们将所有服务器放入优先队列 idle 中，并使用一个时间戳变量 ts 记录当前的时间，其初始值为 0；

  • 随后我们遍历每一个任务：

    • 由于第 i 个任务必须在时间 i 时才可以开始，因此需要将 ts 置为其与 i 的较大值；

    • 我们需要将优先队列 busy 中满足 t \leq \textit{ts 的服务器依次取出并放入优先队列 idle；

    • 如果此时优先队列 idle 中没有服务器，说明我们需要等一台服务器完成任务，因此可以将 ts 置为优先队列 busy 的队首服务器的任务完成时间 t，并再次执行上一步；

    • 此时我们就可以给第 i 个任务安排服务器了，即为优先队列 idle 的队首服务器，将其取出并放入优先队列 busy。

代码

[sol1-C++]
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
class Solution {
private:
    using PLI = pair<long long, int>;
    using PII = pair<int, int>;
    
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        int m = servers.size();
        int n = tasks.size();

        // 工作中的服务器，存储二元组 (t, idx)
        priority_queue<PLI, vector<PLI>, greater<PLI>> busy;
        // 空闲的服务器，存储二元组 (w, idx)
        priority_queue<PII, vector<PII>, greater<PII>> idle;
        for (int i = 0; i < m; ++i) {
            idle.emplace(servers[i], i);
        }
        
        long long ts = 0;
        // 将优先队列 busy 中满足 t<=ts 依次取出并放入优先队列 idle
        auto release = [&]() {
            while (!busy.empty() && busy.top().first <= ts) {
                auto&& [_, idx] = busy.top();
                idle.emplace(servers[idx], idx);
                busy.pop();
            }
        };
        
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            ts = max(ts, static_cast<long long>(i));
            release();
            if (idle.empty()) {
                ts = busy.top().first;
                release();
            }
            auto&& [_, idx] = idle.top();
            ans.push_back(idx);
            busy.emplace(ts + tasks[i], idx);
            idle.pop();
        }
        return ans;
    }
};
[sol1-Python3]
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
class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        # 工作中的服务器，存储二元组 (t, idx)
        busy = list()
        
        # 空闲的服务器，存储二元组 (w, idx)
        idle = [(w, i) for i, w in enumerate(servers)]
        heapq.heapify(idle)
        
        ts = 0
        # 将优先队列 busy 中满足 t<=ts 依次取出并放入优先队列 idle
        def release():
            while busy and busy[0][0] <= ts:
                _, idx = heapq.heappop(busy)
                heapq.heappush(idle, (servers[idx], idx))
        
        ans = list()
        for i, task in enumerate(tasks):
            ts = max(ts, i)
            release()
            if not idle:
                ts = busy[0][0]
                release()
            
            _, idx = heapq.heappop(idle)
            ans.append(idx)
            heapq.heappush(busy, (ts + task, idx))
        
        return ans

复杂度分析

  • 时间复杂度：O((m+n) \log m) 或 O(m + n \log m)，其中 m 和 n 分别是数组 servers 和 tasks 的长度。

    • 我们需要 O(m \log m) 或者 O(m) 的时间将所有服务器放入优先队列 idle，这一步的实现根据使用的 API 而不同。

    • 我们需要 O(n) 的时间遍历任务，对于每一个任务只会安排一台服务器，这一个「安排」的操作会将这台服务器从 idle 移至 busy，并且会在未来的某个时刻因任务完成从 busy 移回 idle，因此对于优先队列的操作次数是均摊 O(1) 的。由于优先队列单词操作的时间复杂度为 O(\log m)，因此总时间复杂度为 O(m \log m)。

  • 空间复杂度：O(m)，即为优先队列 busy 和 idle 需要使用的空间。

 Comments
On this page
1882-使用服务器处理任务