【Leetcode周赛】第243场周赛 T3 - 1882. 使用服务器处理任务 - 中等（堆/优先队列）

发表于 分类于 阅读次数：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

来源：力扣

题目描述

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

解题思路

  这道题目的题干和示例都很长，所以就要求我们能从中提取有效信息，将阅读题抽象成算法题，再挑选合适的数据结构和算法来解决。
  先分析下服务器的分配原则，即优先分配空闲服务器中权重最小的服务器，不难看出这是个动态分配的过程，即下次会分配新的空闲服务器中下一个权重最小的服务器，我们可以每次都去找符合条件的最小值，但是每次都需要遍历一遍数组，时间复杂度为$\mathcal{O}(N)$。
  这时我们应该想到用堆这个数据结构也就是优先队列来处理动态极值的问题，因为我们只关心当前权重最小的服务器，这样无论是分配空闲服务器还是将已经完成工作的服务器放回空闲服务器的时间复杂度都为$\mathcal{O}(logN)$，先设置一个优先队列pq_free处理空闲服务器，其中的元素为(权重，下标)，这样就达到了“优先比权重，权重相同比下标”的目的。
  然后我们发现最先完成工作的服务器优先压回到pq_free中，又是一个动态极值的问题，那么我们可以再为正在工作的服务器设置一个优先队列pq_busy，其中的元素为(预计完成时刻，权重，下标)。这样服务器就可以无缝在这两个状态之间转换，即在两个优先队列之间“流动”。
确定完数据结构还需要注意两点：
1. “如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。”，即为一个任务分配完服务器后先别急着递加时间，先判断同一时刻是否还有空闲服务器以及下一个任务是否准备就绪。
2. 当pq_free为空时，我们不需要再慢慢递加时间t，直接将t设为pq_busy中队首元素对应的预计完成时刻即可，这样可以降低复杂度，如果不这样做其实也没法通过所有用例。

代码（Python）

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
class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        m, n = len(servers), len(tasks)
        ans = [-1] * n
        
        # 设置两个优先队列分别存储空闲的server和正在工作的server
        pq_free, pq_busy = [], []
        # 初始化空闲的server
        for i, s in enumerate(servers):
            heapq.heappush(pq_free, [s, i])

        # j为排到了第几个任务；t表示当前的时间（秒数）
        j, t = 0, 0
        # 条件表示任务未分配完
        while j < n:
            # 表示第j个任务已经就绪
            if t >= j:
                # 如果第j个任务就绪且有空闲server
                if pq_free:
                    # 将权重最低的空闲server弹出pq_free，加上该server完成第
                    # j个任务的时间信息，再压入pq_busy表示该server开始工作
                    s, idx = heapq.heappop(pq_free)
                    heapq.heappush(pq_busy, [t+tasks[j], s, idx])
                    # 完成第j个任务的分配，更新ans和i
                    ans[j] = idx
                    j += 1
                    # 再返回检查当前时刻是否还有空闲server，这是为了满足题目中的
                    # "如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们"
                    continue
                else:
                    # 如果无空闲的服务器，则时间直接跳到将最先完成任务的服务器的对应时刻
                    t = pq_busy[0][0]
            else:
                # 如果第j个任务还没就绪则时间加1
                t += 1
            # 时间改变后将在当前时刻工作已完成的服务器重新放到空闲服务器（pq_free）中
            while pq_busy and pq_busy[0][0] <= t:
                _, s, idx = heapq.heappop(pq_busy)
                heapq.heappush(pq_free, [s, idx])
        return ans