LeetCode 1882：使用服务器处理任务 • Liu Yang's Blog

题目：1882. 使用服务器处理任务

读题

这类模拟题，最麻烦的是读题：

按 tasks 的顺序给服务器分配任务，每次选空闲且 weight 最小的服务器；weight 相同时选下标最小的。
任务在对应时刻才解锁：t = 0 时第 0 个任务解锁，t = 1 时第 1 个任务解锁，依此类推。
答案是每个任务被分配到的服务器下标。

思路

看一眼标签就知道要用优先队列。每次取“最小 weight”，本来也能想到小根堆；weight 相同还要比下标，所以堆里存 (weight, index)。

问题归结为两个操作：取服务器和释放服务器。取服务器很简单，把 servers 堆化后依次弹出即可。关键是怎么表示服务器的占用与释放。

初步思路

维护一个全局时间 time，再用一个数组记录每台服务器的占用截止时间：取用时设为 当前时间 + 任务耗时，释放时逐个检查截止时间是否等于当前时间，是的话放回空闲堆。

优化

上面的做法在释放时要遍历所有服务器。但仔细想想，释放时不也是每次取最早的结束时间和当前时间比较吗？

所以“占用中”的服务器同样可以用小根堆表示，每次压入 (占用截止时间, index)，释放时只需要看堆顶。

两个细节

服务器全部被占用时：让 time 直接跳到忙碌堆堆顶，也就是最早的结束时间，省掉一段没有意义的循环。
任务解锁：time 相当于一个指针，[0, time] 范围内的任务都已经解锁，所以同一时刻可以连续分配多个任务。

实现

代码写得有点丑，凑合看吧：

import heapq
from typing import List


class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        pq, pq_busy, ans = [], [], []
        for k, v in enumerate(servers):
            heapq.heappush(pq, (v, k))
        time, pt = 0, 0
        while pt < len(tasks):
            # 释放已到期的服务器
            while pq_busy and pq_busy[0][0] == time:
                _, idx = heapq.heappop(pq_busy)
                heapq.heappush(pq, (servers[idx], idx))
            # 为已解锁的任务分配服务器（pt <= time 即已解锁）
            while pq and pt <= time and pt < len(tasks):
                _, idx = heapq.heappop(pq)
                heapq.heappush(pq_busy, (time + tasks[pt], idx))
                ans.append(idx)
                pt += 1
            # 推进时间：服务器全忙时直接跳到最早的结束时刻
            time = time + 1 if len(pq_busy) != len(servers) else pq_busy[0][0]
        return ans

整理时只做了等价改写：(time - pt + 1) > 0 写成了更直观的 pt <= time，用 Go 标志控制的释放循环改成了直接判断堆顶。