LeetCode 题解工作台
使用服务器处理任务
给你两个 下标从 0 开始 的整数数组 servers 和 tasks ，长度分别为 n 和 m 。 servers[i] 是第 i 台服务器的 权重 ，而 tasks[j] 是处理第 j 项任务 所需要的时间 （单位：秒）。 你正在…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 堆
答案摘要
我们用一个小根堆 来维护所有的空闲服务器，其中每个元素是一个二元组 $(x, i)$，表示第 台服务器的权重为 。用一个小根堆 来维护所有的忙碌服务器，其中每个元素是一个三元组 $(w, s, i)$，表示第 台服务器在第 秒恢复空闲，权重为 。初始时我们将所有的服务器加入到 中。 接下来，我们遍历所有的任务，对于第 项任务，我们首先将所有在第 秒或之前恢复空闲的服务器从 中移除…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
给你两个 下标从 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 == ntasks.length == m1 <= n, m <= 2 * 1051 <= servers[i], tasks[j] <= 2 * 105
解题思路
方法一：优先队列（小根堆）
我们用一个小根堆 来维护所有的空闲服务器，其中每个元素是一个二元组 ，表示第 台服务器的权重为 。用一个小根堆 来维护所有的忙碌服务器，其中每个元素是一个三元组 ，表示第 台服务器在第 秒恢复空闲，权重为 。初始时我们将所有的服务器加入到 中。
接下来，我们遍历所有的任务，对于第 项任务，我们首先将所有在第 秒或之前恢复空闲的服务器从 中移除，添加到 中。然后我们从 中取出一个权重最小的服务器，将其加入到 中，处理第 项任务。如果 为空，我们从 中取出一个恢复时间最早的服务器，将其加入到 中，处理第 项任务。
遍历结束后，我们得到了答案数组 。
时间复杂度 ，其中 为服务器的数量， 为任务的数量。空间复杂度 。其中 和 分别为服务器和任务的数量。
相似题目：
class Solution:
def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
idle = [(x, i) for i, x in enumerate(servers)]
heapify(idle)
busy = []
ans = []
for j, t in enumerate(tasks):
while busy and busy[0][0] <= j:
_, s, i = heappop(busy)
heappush(idle, (s, i))
if idle:
s, i = heappop(idle)
heappush(busy, (j + t, s, i))
else:
w, s, i = heappop(busy)
heappush(busy, (w + t, s, i))
ans.append(i)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on heap operations for n servers and m tasks, leading to O(m log n) for assignments and free-time updates. Space complexity is O(n + m) due to heaps and tracking the task queue. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Notice the need for two heaps: available and busy servers.
- question_mark
Ask about handling tie-breaking by server index for same weight.
- question_mark
Expect discussion on time simulation per task and efficient queue processing.
常见陷阱
外企场景- error
Failing to update server availability at the correct second can misassign tasks.
- error
Not maintaining tie-breaking by index leads to incorrect output for servers with equal weight.
- error
Assigning tasks without considering the queue order causes timing mismatches.
进阶变体
外企场景- arrow_right_alt
Instead of smallest weight, assign to server with largest weight first.
- arrow_right_alt
Process tasks with variable arrival intervals instead of one per second.
- arrow_right_alt
Allow preemption of tasks on servers with higher weight if a lighter server becomes available.