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

题目描述

这是 LeetCode 上的 1606. 找到处理最多请求的服务器 ，难度为 困难。

你有 $k$ 个服务器，编号为 $0$ 到 $k-1$ ，它们可以同时处理多个请求组。

每个服务器有无穷的计算能力但是不能同时处理超过一个请求。

请求分配到服务器的规则如下：

  • 第 $i$（序号从 $0$ 开始）个请求到达。
  • 如果所有服务器都已被占据，那么该请求被舍弃（完全不处理）。
  • 如果第 ( i % k ) 个服务器空闲，那么对应服务器会处理该请求。
  • 否则，将请求安排给下一个空闲的服务器（服务器构成一个环，必要的话可能从第 $0$ 个服务器开始继续找下一个空闲的服务器）。比方说，如果第 $i$ 个服务器在忙，那么会查看第 ( $i+1$ ) 个服务器，第 ( $i+2$ ) 个服务器等等。
  • 给你一个严格递增的正整数数组 arrival，表示第 $i$ 个任务的到达时间，和另一个数组 load ，其中 $load[i]$ 表示第 $i$ 个请求的工作量（也就是服务器完成它所需要的时间）。你的任务是找到 最繁忙的服务器 。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。

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

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：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：

1
2
3
4
5
6
7
8
输入：k = 3, arrival = [1,2,3,4], load = [1,2,1,2]

输出：[0]

解释：
前 3 个请求分别被前 3 个服务器处理。
请求 3 进来，由于服务器 0 空闲，它被服务器 0 处理。
服务器 0 处理了两个请求，服务器 1 和 2 分别处理了一个请求。所以服务器 0 是最忙的服务器。

示例 3：
1
2
3
4
5
输入：k = 3, arrival = [1,2,3], load = [10,12,11]

输出：[0,1,2]

解释：每个服务器分别处理了一个请求，所以它们都是最忙的服务器。

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

输出：[1]

示例 5：
1
2
3
输入：k = 1, arrival = [1], load = [1]

输出：[0]

提示：

  • $1 <= k <= 10^5$
  • $1 <= arrival.length, load.length <= 10^5$
  • $arrival.length == load.length$
  • $1 <= arrival[i], load[i] <= 10^9$
  • arrival 保证严格递增。

数据结构

题目要统计处理任务数最多的机器，首先容易想到使用「哈希表」统计每个机台处理的任务数，利用机台数量 $k$ 最多不超过 $10^5$，我们可以开一个静态数组 cnts 来充当哈希表，同时维护一个当前处理的最大任务数量 max，最终所有满足 $cnst[i] = \max$ 的机台集合即是答案。

再根据「每个任务有对应的开始时间和持续时间」以及「任务分配规则」，容易想到使用优先队列（堆）和有序集合（红黑树）来进行维护。

具体的，利用「每个任务有对应的开始时间和持续时间」，我们使用优先队列（堆）维护二元组 $(idx, endTime)$，其中 $idx$ 为机器编号，$endTime$ 为当前机台所处理任务的结束时间（也就是该机台最早能够接受新任务的时刻），对于每个 $arrival[i]$ 而言（新任务），我们先从优先队列中取出所有 $endTime \leqslant arrival[i]$ 的机台 $idx$，加入「空闲池」，然后再按照「任务分配规则」从空闲池子中取机台，若取不到，则丢弃该任务。

由于「任务分配规则」是优先取大于等于 i % k 的最小值，若取不到，再取大于等于 $0$ 的最小值。因此我们的「空闲池」最好是支持「二分」的有序集合，容易想到基于「红黑树」的 TreeSet 结构。

Java 代码：

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
class Solution {
    static int N = 100010;
    static int[] cnts = new int[N];
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        Arrays.fill(cnts, 0);
        int n = arrival.length, max = 0;
        PriorityQueue<int[]> busy = new PriorityQueue<>((a,b)->a[1]-b[1]);
        TreeSet<Integer> free = new TreeSet<>();
        for (int i = 0; i < k; i++) free.add(i);
        for (int i = 0; i < n; i++) {
            int start = arrival[i], end = start + load[i];
            while (!busy.isEmpty() && busy.peek()[1] <= start) free.add(busy.poll()[0]);
            Integer u = free.ceiling(i % k);
            if (u == null) u = free.ceiling(0);
            if (u == null) continue;
            free.remove(u);
            busy.add(new int[]{u, end});
            max = Math.max(max, ++cnts[u]);
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (cnts[i] == max) ans.add(i);
        }
        return ans;
    }
}

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from sortedcontainers import SortedList

class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        cnts = [0] * k
        n, m = len(arrival), 0
        busy, free = [], SortedList(range(k))
        for i in range(n):
            start, end = arrival[i], arrival[i] + load[i]
            while busy and busy[0][0] <= start:
                free.add(busy[0][1])
                heappop(busy)
            if (idx := free.bisect_left(i % k)) == len(free) == (idx := free.bisect_left(0)):
                continue
            u = free[idx]
            free.remove(u)
            heappush(busy, (end, u))
            cnts[u] += 1
            m = max(m, cnts[u])
        return [i for i in range(k) if cnts[i] == m]

  • 时间复杂度：令任务数量为 $n$，机台数量为 $k$，起始将所有机台存入 TreeSet，复杂度为 $O(k\log{k})$；每次处理新的 $arrival[i]$ 时，先从优先队列取出可接受新任务的机台，存入 TreeSet，然后从 TreeSet 中取出最多一个的机台来完成任务，其中从 TreeSet 中取出机台最多调用两次的 ceiling 操作，复杂度为 $O(\log{k})$，这部分的整体复杂度为 $O(n\log{k})$；统计处理任务数达到 max 的机台集合复杂度为 $O(k)$；整体复杂度为 $O((k + n)\log{k})$
  • 空间复杂度：$O(k)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1606 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。