使用服务器处理任务

题目

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

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

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

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

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

返回答案数组 ans​​​​ 。

示例

示例1

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


示例2

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


提示

• $servers.length\&＃61;\&＃61;n$
• $tasks.length\&＃61;\&＃61;m$
• 1<&＃61;n,m<&＃61;2∗1051 <&＃61; n, m <&＃61; 2 * 10^51<&＃61;n,m<&＃61;2∗105
• 1<&＃61;servers[i],tasks[j]<&＃61;2∗1051 <&＃61; servers[i], tasks[j] <&＃61; 2 * 10^51<&＃61;servers[i],tasks[j]<&＃61;2∗105

题解

方法一&＃xff1a;优先队列

思路与算法

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

• 优先队列 $busy$ 存储工作中的服务器&＃xff0c;每一台服务器用二元组 $(t,idx)$ 表示&＃xff0c;其中 $t$ 为该服务器结束工作的时间&＃xff0c;$idx$ 为该服务器的编号。优先队列的队首服务器满足 $t$ 最小&＃xff0c;并且在 $t$ 相同的情况下&＃xff0c;$idx$ 最小。
• 优先队列$idle$ 存储空闲的服务器&＃xff0c;每一台服务器用二元组 $(w,idx)$表示&＃xff0c;其中 $w$ 为该服务器的 $weight$&＃xff0c;$idx$为该服务器的编号。优先队列的队首服务器满足 $w$ 最小&＃xff0c;并且在 $w$ 相同的情况下&＃xff0c;$idx$ 最小。

这样设计的好处在于&＃xff1a;

• 随着时间的增加&＃xff0c;我们可以依次从优先队列 $busy$ 中取出已经工作完成&＃xff08;即时间大于等于 $t$&＃xff09;的服务器&＃xff1b;
• 当我们需要给任务安排服务器时&＃xff0c;我们可以依次从优先队列 $idle$ 中取出可用的服务器。

因此&＃xff0c;我们就可以设计出算法的流程&＃xff1a;

• 在初始时&＃xff0c;我们将所有服务器放入优先队列 $idle$ 中&＃xff0c;并使用一个时间戳变量 $ts$ 记录当前的时间&＃xff0c;其初始值为$0$&＃xff1b;
• 随后我们遍历每一个任务&＃xff1a;
  • 由于第$i$ 个任务必须在时间$i$ 时才可以开始&＃xff0c;因此需要将 $ts$ 置为其与 $i$的较大值&＃xff1b;
  • 我们需要将优先队列 $busy$ 中满足 $t\le ts$ 的服务器依次取出并放入优先队列 $idle$&＃xff1b;
  • 如果此时优先队列 $idle$ 中没有服务器&＃xff0c;说明我们需要等一台服务器完成任务&＃xff0c;因此可以将 $ts$ 置为优先队列$busy$ 的队首服务器的任务完成时间 $t$&＃xff0c;并再次执行上一步&＃xff1b;
  • 此时我们就可以给第$i$ 个任务安排服务器了&＃xff0c;即为优先队列 $idle$ 的队首服务器&＃xff0c;将其取出并放入优先队列 $busy$。

代码

class Solution:def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:# 工作中的服务器&＃xff0c;存储二元组 (t, idx)busy &＃61; list()# 空闲的服务器&＃xff0c;存储二元组 (w, idx)idle &＃61; [(w, i) for i, w in enumerate(servers)]heapq.heapify(idle)ts &＃61; 0# 将优先队列 busy 中满足 t<&＃61;ts 依次取出并放入优先队列 idledef release():while busy and busy[0][0] <&＃61; ts:_, idx &＃61; heapq.heappop(busy)heapq.heappush(idle, (servers[idx], idx))ans &＃61; list()for i, task in enumerate(tasks):ts &＃61; max(ts, i)release()if not idle:ts &＃61; busy[0][0]release()_, idx &＃61; heapq.heappop(idle)ans.append(idx)heapq.heappush(busy, (ts &＃43; task, idx))return ans


复杂度分析

• 时间复杂度&＃xff1a;$O((m\&＃43;n)logm)$ 或 $O(m\&＃43;nlogm)$&＃xff0c;其中 $m$ 和$n$ 分别是数组$servers$ 和$tasks$ 的长度。
  • 我们需要 $O(mlogm)$ 或者$O(m)$ 的时间将所有服务器放入优先队列 $idle$&＃xff0c;这一步的实现根据使用的 $API$ 而不同。
  • 我们需要$O(n)$的时间遍历任务&＃xff0c;对于每一个任务只会安排一台服务器&＃xff0c;这一个「安排」的操作会将这台服务器从$idle$ 移至 $busy$&＃xff0c;并且会在未来的某个时刻因任务完成从 $busy$ 移回 $idle$&＃xff0c;因此对于优先队列的操作次数是均摊 $O(1)$ 的。由于优先队列单词操作的时间复杂度为$O(logm)$&＃xff0c;因此总时间复杂度为$O(mlogm)$。
• 空间复杂度&＃xff1a;$O(m)$&＃xff0c;即为优先队列 $busy$ 和 $idle$ 需要使用的空间