题目
给你两个 下标从 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 秒。
提示
- s e r v e r s . l e n g t h = = n servers.length == n servers.length==n
- t a s k s . l e n g t h = = m tasks.length == m tasks.length==m
- 1 < = n , m < = 2 ∗ 1 0 5 1 <= n, m <= 2 * 10^5 1<=n,m<=2∗105
- 1 < = s e r v e r s [ i ] , t a s k s [ j ] < = 2 ∗ 1 0 5 1 <= servers[i], tasks[j] <= 2 * 10^5 1<=servers[i],tasks[j]<=2∗105
题解
方法一：优先队列
思路与算法
我们使用两个优先队列分别存储工作中的服务器以及空闲的服务器：
- 优先队列 b u s y busy busy 存储工作中的服务器，每一台服务器用二元组 ( t , i d x ) (t,idx) (t,idx) 表示，其中 t t t 为该服务器结束工作的时间， i d x idx idx 为该服务器的编号。优先队列的队首服务器满足 t t t 最小，并且在 t t t 相同的情况下， i d x idx idx 最小。
- 优先队列 i d l e idle idle 存储空闲的服务器，每一台服务器用二元组 ( w , i d x ) (w,idx) (w,idx)表示，其中 w w w 为该服务器的 w e i g h t weight weight， i d x idx idx为该服务器的编号。优先队列的队首服务器满足 w w w 最小，并且在 w w w 相同的情况下， i d x idx idx 最小。
这样设计的好处在于：
- 随着时间的增加，我们可以依次从优先队列 b u s y busy busy 中取出已经工作完成（即时间大于等于 t t t）的服务器；
- 当我们需要给任务安排服务器时，我们可以依次从优先队列 i d l e idle idle 中取出可用的服务器。
因此，我们就可以设计出算法的流程：
- 在初始时，我们将所有服务器放入优先队列 i d l e idle idle 中，并使用一个时间戳变量 t s ts ts 记录当前的时间，其初始值为 0 0 0；
- 随后我们遍历每一个任务：
- 由于第 i i i 个任务必须在时间 i i i 时才可以开始，因此需要将 t s ts ts 置为其与 i i i的较大值；
- 我们需要将优先队列 b u s y busy busy 中满足 t ≤ t s t≤ts t≤ts 的服务器依次取出并放入优先队列 i d l e idle idle；
- 如果此时优先队列 i d l e idle idle 中没有服务器，说明我们需要等一台服务器完成任务，因此可以将 t s ts ts 置为优先队列 b u s y busy busy 的队首服务器的任务完成时间 t t t，并再次执行上一步；
- 此时我们就可以给第 i i i 个任务安排服务器了，即为优先队列 i d l e idle idle 的队首服务器，将其取出并放入优先队列 b u s y busy busy。
代码
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
)
l
o
g
m
)
O((m+n)logm)
O((m+n)logm) 或
O
(
m
+
n
l
o
g
m
)
O(m+nlogm)
O(m+nlogm)，其中
m
m
m 和
n
n
n 分别是数组
s
e
r
v
e
r
s
servers
servers 和
t
a
s
k
s
tasks
tasks 的长度。
- 我们需要 O ( m l o g m ) O(mlogm) O(mlogm) 或者 O ( m ) O(m) O(m) 的时间将所有服务器放入优先队列 i d l e idle idle，这一步的实现根据使用的 A P I API API 而不同。
- 我们需要 O ( n ) O(n) O(n)的时间遍历任务，对于每一个任务只会安排一台服务器，这一个「安排」的操作会将这台服务器从 i d l e idle idle 移至 b u s y busy busy，并且会在未来的某个时刻因任务完成从 b u s y busy busy 移回 i d l e idle idle，因此对于优先队列的操作次数是均摊 O ( 1 ) O(1) O(1) 的。由于优先队列单词操作的时间复杂度为 O ( l o g m ) O(logm) O(logm)，因此总时间复杂度为 O ( m l o g m ) O(mlogm) O(mlogm)。
- 空间复杂度： O ( m ) O(m) O(m)，即为优先队列 b u s y busy busy 和 i d l e idle idle 需要使用的空间