使用服务器处理任务

难度: Medium

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

Submission

运行时间: 577 ms

内存: 58.9 MB

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        idle, busy = [], []
        for i, weight in enumerate(servers):
            heappush(idle, (weight, i))
        res = []
        for start, cost in enumerate(tasks):
            while busy and busy[0][0] <= start:
                _, s, i = heappop(busy)
                heappush(idle, (s, i))
            if idle:
                s, i = heappop(idle)
                heappush(busy, (start + cost, s, i))
            else:
                t, s, i = heappop(busy)
                heappush(busy, (t + cost, s, i))
            res.append(i)
        return res

Explain

该题解使用了两个优先队列（堆）来管理服务器的状态：一个是空闲服务器堆（idle），另一个是忙碌服务器堆（busy）。空闲服务器堆按服务器权重和索引排序，确保总是从权重最小且索引最小的服务器分配任务。忙碌服务器堆则按服务器空闲的时间、权重和索引排序，确保最早空闲的服务器可以重新被分配。对于每一个任务，首先检查是否有服务器已经完成任务并因此变为空闲，如果有，则将其从忙碌堆移到空闲堆。然后，如果有空闲的服务器，立即分配当前任务；如果没有，则从忙碌堆中取出最早空闲的服务器，并将其继续排入忙碌堆，更新其空闲时间。最后记录分配的服务器索引。

时间复杂度: O(m log n)

空间复杂度: O(n)

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        idle, busy = [], []  # 空闲和忙碌的服务器堆
        for i, weight in enumerate(servers):  # 初始化空闲服务器堆
            heappush(idle, (weight, i))
        res = []  # 存储任务分配结果的列表
        for start, cost in enumerate(tasks):  # 遍历任务
            while busy and busy[0][0] <= start:  # 释放已经空闲的服务器
                _, s, i = heappop(busy)
                heappush(idle, (s, i))
            if idle:  # 有空闲服务器时直接分配
                s, i = heappop(idle)
                heappush(busy, (start + cost, s, i))  # 更新服务器状态为忙碌
            else:  # 无空闲服务器时等待最早的一个
                t, s, i = heappop(busy)
                heappush(busy, (t + cost, s, i))  # 更新服务器忙碌时间
            res.append(i)  # 记录任务分配的服务器索引
        return res

Explore

在题解中，我们使用了一个最小堆（优先队列）来处理空闲服务器。堆中的元素是一个元组，其中包括服务器的权重和索引，且元组的排序首先是按权重升序，其次是按索引升序。这样的排序规则确保了每次从空闲堆中取出的服务器都是当前权重最小的，如果权重相同则取索引最小的。因此，当多项任务等待和多台服务器同时空闲时，堆的这种特性保证了能够按照题目要求的权重最小和下标最小的规则进行服务器的分配。

使用两个优先队列（堆）来管理服务器状态的主要理由是优先队列能够有效地支持动态数据的插入和删除操作，并且能够保证每次取出的都是最优（最小或最大）的元素。在这个场景中，一个优先队列用于管理空闲服务器，另一个用于管理忙碌服务器。空闲服务器堆能够确保每次都能快速地按权重和索引的优先级分配服务器，而忙碌服务器堆则按服务器空闲的时间排序，这样可以确保最早空闲的服务器能够优先重新被分配。如果使用列表或单一队列，我们不仅需要手动维护排序，每次服务器状态更新时还可能需要进行复杂的插入或删除操作，这会使得时间复杂度上升，效率降低。因此，两个优先队列的使用是为了最大化效率和符合题目分配逻辑的需要。