千问 LeetCode 1606.找到处理最多请求的服务器 public List<Integer> busiestServers(int k, int[] arrival, int[] load)
为什么用它?如果找不到,再找最小的编号(即从头开始找),这完美契合了“环形查找”的需求。*处理请求:如果找到了空闲服务器,将其从 free 移除,加入 busy(结束时间为 arrival[i] + load[i]),并增加该服务器的处理计数。*如果找不到(说明 target 及其后面的都忙),则找 free 中最小的值(first(),即从 0 开始找)。2.分配服务器:根据题目规则(优先 (i
这是一道经典的模拟题,主要考察对优先队列(堆)和有序集合(TreeSet)的灵活运用。
📌 核心思路
我们需要模拟请求到达和处理的过程。对于每一个请求,我们需要做两件事:
1. 释放服务器:检查有哪些服务器在当前请求到达时已经完成了任务,将它们从“忙碌”状态变为“空闲”状态。
2. 分配服务器:根据题目规则(优先 (i % k),否则找下一个空闲的),在空闲服务器中找到合适的一个来处理当前请求。
🛠️ 数据结构选择
为了高效地完成上述操作,我们使用以下数据结构:
1. TreeSet free:
* 用来存储当前空闲服务器的编号。
* 为什么用它? 题目要求如果 (i % k) 被占用,要找“下一个”空闲服务器。TreeSet 是有序的,我们可以使用 ceiling(x) 方法快速找到大于等于 x 的最小编号。如果找不到,再找最小的编号(即从头开始找),这完美契合了“环形查找”的需求。
2. PriorityQueue busy:
* 用来存储当前忙碌的服务器,按任务结束时间从小到大排序(小顶堆)。
* 数组元素为 [结束时间, 服务器编号]。
* 为什么用它? 每次新请求到达时,我们需要知道哪些服务器已经空闲了。通过堆顶元素,我们可以快速判断最早结束的任务是否在当前时间之前完成。
📝 步骤详解
1. 初始化:所有 0 到 k-1 的服务器一开始都是空闲的,加入 free 集合。
2. 遍历请求:对于第 i 个请求(到达时间 arrival[i],耗时 load[i]):
* 更新状态:检查 busy 堆顶,如果堆顶任务的结束时间 = target 的最小值(ceiling(target))。
* 如果找不到(说明 target 及其后面的都忙),则找 free 中最小的值(first(),即从 0 开始找)。
* 处理请求:如果找到了空闲服务器,将其从 free 移除,加入 busy(结束时间为 arrival[i] + load[i]),并增加该服务器的处理计数。
3. 统计结果:遍历计数数组,找出处理请求数最多的服务器编号。
💻 Java 代码实现
import java.util.*;
class Solution {
public List busiestServers(int k, int[] arrival, int[] load) {
// 1. 初始化数据结构
// 存储空闲服务器编号,TreeSet 保证有序,方便查找 >= target 的最小值
TreeSet free = new TreeSet();
for (int i = 0; i busy = new PriorityQueue((a, b) -> a[0] - b[0]);
// 统计每个服务器处理的请求数
int[] count = new int[k];
// 2. 遍历每个请求
for (int i = 0; i = target 的最小空闲服务器
selectedServer = free.ceiling(target);
// 如果找不到(说明 target 到 k-1 都在忙),则找从头开始找(0 到 target-1)
if (selectedServer == null) {
selectedServer = free.first();
}
// 6. 分配请求
// 从空闲集合移除
free.remove(selectedServer);
// 加入忙碌队列
busy.offer(new int[]{endTime, selectedServer});
// 计数加一
count[selectedServer]++;
}
// 7. 找出处理请求最多的服务器
List result = new ArrayList();
int maxRequests = 0;
for (int c : count) {
maxRequests = Math.max(maxRequests, c);
}
for (int i = 0; i < k; i++) {
if (count[i] == maxRequests) {
result.add(i);
}
}
return result;
}
}
⏱️ 复杂度分析
* 时间复杂度:O((n + k) log k)
* 初始化 TreeSet 需要 O(k log k)。
* 遍历 n 个请求,每个请求最多进出 TreeSet 和 PriorityQueue 一次。TreeSet 的查找(ceiling)、插入、删除操作均为 O(log k),堆操作也是 O(log k)。
* 空间复杂度:O(k)
* free 集合和 busy 堆最多存储 k 个元素,count 数组长度为 k。
💡 关键点提示
* free.ceiling(target) 是解题的核心,它避免了线性扫描查找下一个空闲服务器,大大降低了时间复杂度。
* 注意处理环形查找的逻辑:如果 ceiling 返回 null,记得回退到 first()。
更多推荐




所有评论(0)