找到处理最多请求的服务器

难度: Hard

你有 k 个服务器，编号为 0 到 k-1 ，它们可以同时处理多个请求组。每个服务器有无穷的计算能力但是 不能同时处理超过一个请求 。请求分配到服务器的规则如下：

第 i （序号从 0 开始）个请求到达。
如果所有服务器都已被占据，那么该请求被舍弃（完全不处理）。
如果第 (i % k) 个服务器空闲，那么对应服务器会处理该请求。
否则，将请求安排给下一个空闲的服务器（服务器构成一个环，必要的话可能从第 0 个服务器开始继续找下一个空闲的服务器）。比方说，如果第 i 个服务器在忙，那么会查看第 (i+1) 个服务器，第 (i+2) 个服务器等等。

给你一个 严格递增 的正整数数组 arrival ，表示第 i 个任务的到达时间，和另一个数组 load ，其中 load[i] 表示第 i 个请求的工作量（也就是服务器完成它所需要的时间）。你的任务是找到 最繁忙的服务器 。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。

请你返回包含所有 最繁忙服务器 序号的列表，你可以以任意顺序返回这个列表。

示例 1：

输入：k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] 
输出：[1] 
解释：
所有服务器一开始都是空闲的。
前 3 个请求分别由前 3 台服务器依次处理。
请求 3 进来的时候，服务器 0 被占据，所以它被安排到下一台空闲的服务器，也就是服务器 1 。
请求 4 进来的时候，由于所有服务器都被占据，该请求被舍弃。
服务器 0 和 2 分别都处理了一个请求，服务器 1 处理了两个请求。所以服务器 1 是最忙的服务器。

示例 2：

输入：k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
输出：[0]
解释：
前 3 个请求分别被前 3 个服务器处理。
请求 3 进来，由于服务器 0 空闲，它被服务器 0 处理。
服务器 0 处理了两个请求，服务器 1 和 2 分别处理了一个请求。所以服务器 0 是最忙的服务器。

示例 3：

输入：k = 3, arrival = [1,2,3], load = [10,12,11]
输出：[0,1,2]
解释：每个服务器分别处理了一个请求，所以它们都是最忙的服务器。

示例 4：

输入：k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2]
输出：[1]

示例 5：

输入：k = 1, arrival = [1], load = [1]
输出：[0]

提示：

1 <= k <= 10⁵
1 <= arrival.length, load.length <= 10⁵
arrival.length == load.length
1 <= arrival[i], load[i] <= 10⁹
arrival 保证 严格递增 。

Submission

运行时间: 322 ms

内存: 38.0 MB

class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        available = list(range(k))
        busy = []
        requests = [0] * k
        for i, (start, t) in enumerate(zip(arrival, load)):
            while busy and busy[0][0] <= start:
                _, id = heappop(busy)
                heappush(available, i + (id - i) % k)  # 利用 Python 负数取模变成同余的非负数的性质
            if available:
                id = heappop(available) % k
                requests[id] += 1
                heappush(busy, (start + t, id))
        maxRequest = max(requests)
        return [i for i, req in enumerate(requests) if req == maxRequest]

Explain

该题解采用了两个堆结构，一个表示可用服务器的堆（available），另一个表示忙碌服务器的堆（busy）。首先，所有服务器都是空闲的，因此将它们的索引加入到可用服务器堆中。对于每个请求，首先检查忙碌堆中是否有已经完成任务的服务器，如果有，则将其从忙碌堆中移除，并重新加入到可用堆中。之后，从可用堆中取出一个服务器处理当前请求，并将其加入到忙碌堆中。如果可用堆为空，则当前请求被丢弃。最后，统计每个服务器处理的请求数量，返回处理最多请求的服务器。

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

空间复杂度: O(k)

class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        available = list(range(k))  # 初始化所有服务器为可用
        busy = []  # 忙碌服务器堆
        requests = [0] * k  # 每个服务器的请求数量
        for i, (start, t) in enumerate(zip(arrival, load)):
            # 释放已经完成的服务器
            while busy and busy[0][0] <= start:
                _, id = heappop(busy)
                heappush(available, i + (id - i) % k)  # 重新计算服务器索引并加入可用堆
            if available:
                id = heappop(available) % k  # 从可用堆中获取一个服务器
                requests[id] += 1  # 更新该服务器的请求数量
                heappush(busy, (start + t, id))  # 将服务器加入忙碌堆
        maxRequest = max(requests)  # 找到最大的请求数
        return [i for i, req in enumerate(requests) if req == maxRequest]  # 返回请求数最多的服务器列表

Explore

这种索引计算方式是为了保持服务器处理请求的循环性。在这个场景中，服务器是以循环的方式处理请求的，即第 i 个请求应该由第 (i % k) 号服务器处理。当服务器从忙碌堆释放并重新加入到可用堆时，我们需要确保它在正确的位置上以保持处理请求的顺序。计算 `i + (id - i) % k` 实际上是为了计算下一个请求编号，该编号对应服务器 id 应当重新开始处理的位置。这样可以确保每个服务器都有机会按顺序处理接下来的请求。

`start + t` 表示服务器完成当前请求的具体时间点。当我们将服务器及其完成时间（`start + t`）添加到忙碌堆时，这使我们能够按照服务器变为空闲的时间顺序来管理它们。使用最小堆结构，我们可以快速地从堆中得到最先完成任务的服务器，从而在该服务器变为可用时及时将其重新加入到可用堆中，提高服务器的利用率。

这种情况下，由于没有任何服务器可用（无论是因为它们都处于忙碌状态，或者已经被分配出去），请求将不得不被丢弃。这种设计确保了只有在所有服务器都正忙且无法处理新请求时，请求才会被丢弃，从而尽可能地利用服务器资源。

是的，这种设计确实可能导致在某些极端情况下，如请求到达的频率极高或服务器处理请求的时间较长时，服务器的利用率会很低，因为新的请求可能会因为没有可用服务器而被丢弃。这一点突显了在设计服务器负载均衡策略时，需要根据实际的请求到达率和服务器处理能力来优化参数和策略，以提高服务器的整体利用率和响应能力。