Hard

题目描述

你有 k 个编号从 0 到 k-1 的服务器，它们可以同时处理多个请求。每个服务器都有无限的计算能力，但不能同时处理超过一个请求。请求按照特定算法分配给服务器：

  • 第 i（从 0 开始索引）个请求到达。
  • 如果所有服务器都在忙，该请求被丢弃（完全不处理）。
  • 如果第 (i % k) 个服务器可用，将请求分配给该服务器。
  • 否则，将请求分配给下一个可用的服务器（在服务器列表中循环，必要时从 0 开始）。例如，如果第 i 个服务器忙，尝试将请求分配给第 (i+1) 个服务器，然后是第 (i+2) 个服务器，依此类推。

给你一个严格递增的正整数数组 arrival，其中 arrival[i] 表示第 i 个请求的到达时间，以及另一个数组 load，其中 load[i] 表示第 i 个请求的负载（完成所需的时间）。你的目标是找到最忙的服务器。如果一个服务器在所有服务器中成功处理了最多的请求数，则认为它是最忙的。

返回包含最忙服务器 ID（从 0 开始索引）的列表。你可以按任何顺序返回 ID。

示例 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：

输入：k = 3, arrival = [1,2,3], load = [10,12,11]
输出：[0,1,2]

约束条件：

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

解题思路

解题思路

这道题需要模拟服务器处理请求的过程，核心挑战在于高效地找到下一个可用服务器。

算法分析

  1. 数据结构选择：

    • 使用最小堆追踪服务器的结束时间
    • 使用有序集合（如 set）维护可用服务器列表
    • 计数器记录每个服务器处理的请求数

  2. 处理流程：

    • 对于每个到达的请求，首先更新可用服务器列表（检查哪些服务器已完成任务）
    • 从首选服务器 i % k 开始，在可用服务器中找到下一个可用的
    • 如果找到可用服务器，分配请求并更新相关数据结构
    • 如果没有可用服务器，丢弃请求

  3. 关键优化：

    • 使用 lower_bound 快速找到从指定位置开始的第一个可用服务器
    • 如果没找到，需要循环回到开头继续查找
    • 堆的使用确保我们能快速获知最早完成的任务时间

时间复杂度分析

  • 每个请求最多需要 O(log k) 时间来查找可用服务器
  • 堆操作的时间复杂度为 O(log k)
  • 总时间复杂度：O(n log k)，其中 n 是请求数量

代码实现

class Solution {
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
        set<int> available;
        for (int i = 0; i < k; i++) {
            available.insert(i);
        }
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> busy;
        vector<int> count(k, 0);
        
        for (int i = 0; i < arrival.size(); i++) {
            int arrTime = arrival[i];
            int loadTime = load[i];
            
            while (!busy.empty() && busy.top().first <= arrTime) {
                available.insert(busy.top().second);
                busy.pop();
            }
            
            if (available.empty()) continue;
            
            int preferred = i % k;
            auto it = available.lower_bound(preferred);
            
            if (it == available.end()) {
                it = available.begin();
            }
            
            int server = *it;
            available.erase(it);
            busy.push({arrTime + loadTime, server});
            count[server]++;
        }
        
        int maxCount = *max_element(count.begin(), count.end());
        vector<int> result;
        for (int i = 0; i < k; i++) {
            if (count[i] == maxCount) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        import heapq
        from sortedcontainers import SortedList
        
        available = SortedList(range(k))
        busy = []
        count = [0] * k
        
        for i, (arr_time, load_time) in enumerate(zip(arrival, load)):
            while busy and busy[0][0] <= arr_time:
                _, server = heapq.heappop(busy)
                available.add(server)
            
            if not available:
                continue
            
            preferred = i % k
            idx = available.bisect_left(preferred)
            
            if idx == len(available):
                idx = 0
            
            server = available.pop(idx)
            heapq.heappush(busy, (arr_time + load_time, server))
            count[server] += 1
        
        max_count = max(count)
        return [i for i in range(k) if count[i] == max_count]

public class Solution {
    public IList<int> BusiestServers(int k, int[] arrival, int[] load) {
        var available = new SortedSet<int>();
        for (int i = 0; i < k; i++) {
            available.Add(i);
        }
        
        var busy = new PriorityQueue<(int endTime, int server), int>();
        var count = new int[k];
        
        for (int i = 0; i < arrival.Length; i++) {
            int arrTime = arrival[i];
            int loadTime = load[i];
            
            while (busy.Count > 0 && busy.Peek().endTime <= arrTime) {
                var (_, server) = busy.Dequeue();
                available.Add(server);
            }
            
            if (available.Count == 0) continue;
            
            int preferred = i % k;
            var serverToUse = available.GetViewBetween(preferred, int.MaxValue).Min;
            
            if (serverToUse == 0 && preferred > 0) {
                serverToUse = available.Min;
            }
            
            available.Remove(serverToUse);
            busy.Enqueue((arrTime + loadTime, serverToUse), arrTime + loadTime);
            count[serverToUse]++;
        }
        
        int maxCount = count.Max();
        var result = new List<int>();
        for (int i = 0; i < k; i++) {
            if (count[i] == maxCount) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

var busiestServers = function(k, arrival, load) {
    const requests = new Array(k).fill(0);
    const available = new Set();
    const busy = [];
    
    for (let i = 0; i < k; i++) {
        available.add(i);
    }
    
    for (let i = 0; i < arrival.length; i++) {
        const currentTime = arrival[i];
        
        while (busy.length && busy[0][0] <= currentTime) {
            const [, serverId] = busy.shift();
            available.add(serverId);
        }
        
        if (available.size === 0) continue;
        
        let server = -1;
        const preferred = i % k;
        
        if (available.has(preferred)) {
            server = preferred;
        } else {
            const sortedAvailable = Array.from(available).sort((a, b) => a - b);
            
            let found = false;
            for (const s of sortedAvailable) {
                if (s >= preferred) {
                    server = s;
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                server = sortedAvailable[0];
            }
        }
        
        available.delete(server);
        requests[server]++;
        
        const endTime = currentTime + load[i];
        busy.push([endTime, server]);
        busy.sort((a, b) => a[0] - b[0]);
    }
    
    const maxRequests = Math.max(...requests);
    const result = [];
    
    for (let i = 0; i < k; i++) {
        if (requests[i] === maxRequests) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log k)n为请求数，每个请求需要O(log k)时间进行堆操作和有序集合查找
空间复杂度O(k)需要存储k个服务器的状态信息

相关题目