这是一道经典的模拟题,主要考察对优先队列(堆)和有序集合(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()。

 

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐