题目形容
这是 LeetCode 上的 1606. 找到解决最多申请的服务器 ，难度为 艰难。
Tag :「数据结构」、「优先队列（堆）」、「红黑树」、「二分」
你有 $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^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 代码：
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 代码：
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/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布