Medium

题目描述

给你两个 下标从 0 开始 的整数数组 servers 和 tasks ，长度分别为 n 和 m 。servers[i] 是第 i 个服务器的 权重 ，tasks[j] 是处理第 j 个任务 所需要的时间（单位：秒）。

任务是按照一个任务队列的顺序分配给服务器的。最初，所有服务器都是空闲的，队列也是空的。

在第 j 秒时，第 j 个任务被插入队列中（从第 0 个任务在第 0 秒被插入开始）。只要有空闲的服务器且队列不为空，队列中最前面的任务将被分配给 权重最小 的空闲服务器。如果权重相同，则分配给 下标最小 的空闲服务器。

如果没有空闲的服务器且队列不为空，我们需要等待直到有服务器变成空闲，然后立即分配下一个任务。如果多个服务器同时变成空闲，那么将根据权重和下标的优先级按插入顺序依次分配多个任务。

在第 t 秒分配到第 j 个任务的服务器会在第 t + tasks[j] 秒时变成空闲。

请你构建长度为 m 的答案数组 ans ，其中 ans[j] 是第 j 个任务分配的服务器下标。

返回数组 ans 。

示例 1：

输入：servers = [3,3,2], tasks = [1,2,3,2,1,2]
输出：[2,2,0,2,1,2]
解释：事件按时间顺序如下：
- 第 0 秒，添加第 0 个任务，使用服务器 2 处理到第 1 秒。
- 第 1 秒，服务器 2 变空闲。添加第 1 个任务，使用服务器 2 处理到第 3 秒。
- 第 2 秒，添加第 2 个任务，使用服务器 0 处理到第 5 秒。
- 第 3 秒，服务器 2 变空闲。添加第 3 个任务，使用服务器 2 处理到第 5 秒。
- 第 4 秒，添加第 4 个任务，使用服务器 1 处理到第 5 秒。
- 第 5 秒，所有服务器都变空闲。添加第 5 个任务，使用服务器 2 处理到第 7 秒。

示例 2：

输入：servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
输出：[1,4,1,4,1,3,2]

提示：

  • servers.length == n
  • tasks.length == m
  • 1 <= n, m <= 2 * 10^5
  • 1 <= servers[i], tasks[j] <= 2 * 10^5

解题思路

这道题目需要模拟服务器处理任务的过程，关键在于维护两个优先队列来管理服务器状态。

核心思路

  1. 双优先队列管理：

    • 空闲服务器队列：按照权重升序，权重相同时按下标升序
    • 忙碌服务器队列：按照完成时间升序排列

  2. 时间推进策略：

    • 当前时间有新任务到达时，优先分配给空闲服务器
    • 如果没有空闲服务器，需要等待到最早完成任务的时间点
    • 每次处理完成的服务器都要重新加入空闲队列

  3. 任务分配规则：

    • 选择权重最小的空闲服务器，权重相同选择下标最小的
    • 使用优先队列可以自动维护这个优先级

算法流程

  1. 初始化两个优先队列和结果数组
  2. 将所有服务器加入空闲队列
  3. 对每个任务按时间顺序处理：
    • 将当前时间之前完成的服务器移回空闲队列
    • 如果有空闲服务器，直接分配；否则等待最早的服务器完成
    • 记录分配结果，将服务器加入忙碌队列

这种方法能够高效处理大规模数据，时间复杂度为 O(m log n)，其中 m 是任务数，n 是服务器数。

代码实现

class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        int n = servers.size(), m = tasks.size();
        vector<int> ans(m);
        
        // 空闲服务器堆：{权重, 下标}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> available;
        // 忙碌服务器堆：{完成时间, 下标}
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> busy;
        
        for (int i = 0; i < n; i++) {
            available.push({servers[i], i});
        }
        
        long long time = 0;
        for (int i = 0; i < m; i++) {
            time = max(time, (long long)i);
            
            // 将完成的服务器移回可用堆
            while (!busy.empty() && busy.top().first <= time) {
                int idx = busy.top().second;
                busy.pop();
                available.push({servers[idx], idx});
            }
            
            // 如果没有可用服务器，等待最早完成的服务器
            if (available.empty()) {
                time = busy.top().first;
                while (!busy.empty() && busy.top().first <= time) {
                    int idx = busy.top().second;
                    busy.pop();
                    available.push({servers[idx], idx});
                }
            }
            
            // 分配任务
            int serverIdx = available.top().second;
            available.pop();
            ans[i] = serverIdx;
            busy.push({time + tasks[i], serverIdx});
        }
        
        return ans;
    }
};

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        import heapq
        
        n, m = len(servers), len(tasks)
        ans = [0] * m
        
        # 空闲服务器堆：[权重, 下标]
        available = [[servers[i], i] for i in range(n)]
        heapq.heapify(available)
        
        # 忙碌服务器堆：[完成时间, 下标]
        busy = []
        
        time = 0
        for i in range(m):
            time = max(time, i)
            
            # 将完成的服务器移回可用堆
            while busy and busy[0][0] <= time:
                end_time, idx = heapq.heappop(busy)
                heapq.heappush(available, [servers[idx], idx])
            
            # 如果没有可用服务器，等待最早完成的服务器
            if not available:
                time = busy[0][0]
                while busy and busy[0][0] <= time:
                    end_time, idx = heapq.heappop(busy)
                    heapq.heappush(available, [servers[idx], idx])
            
            # 分配任务
            weight, server_idx = heapq.heappop(available)
            ans[i] = server_idx
            heapq.heappush(busy, [time + tasks[i], server_idx])
        
        return ans

public class Solution {
    public int[] AssignTasks(int[] servers, int[] tasks) {
        int n = servers.Length, m = tasks.Length;
        int[] ans = new int[m];
        
        // 空闲服务器堆：(权重, 下标)
        var available = new SortedSet<(int weight, int index)>();
        // 忙碌服务器堆：(完成时间, 下标)
        var busy = new SortedSet<(long endTime, int index)>();
        
        for (int i = 0; i < n; i++) {
            available.Add((servers[i], i));
        }
        
        long time = 0;
        for (int i = 0; i < m; i++) {
            time = Math.Max(time, i);
            
            // 将完成的服务器移回可用集合
            while (busy.Count > 0 && busy.Min.endTime <= time) {
                var (endTime, idx) = busy.Min;
                busy.Remove(busy.Min);
                available.Add((servers[idx], idx));
            }
            
            // 如果没有可用服务器，等待最早完成的服务器
            if (available.Count == 0) {
                time = busy.Min.endTime;
                while (busy.Count > 0 && busy.Min.endTime <= time) {
                    var (endTime, idx) = busy.Min;
                    busy.Remove(busy.Min);
                    available.Add((servers[idx], idx));
                }
            }
            
            // 分配任务
            var (weight, serverIdx) = available.Min;
            available.Remove(available.Min);
            ans[i] = serverIdx;
            busy.Add((time + tasks[i], serverIdx));
        }
        
        return ans;
    }
}

var assignTasks = function(servers, tasks) {
    const n = servers.length, m = tasks.length;
    const ans = new Array(m);
    
    // 空闲服务器堆：[权重, 下标]
    const available = new MinPriorityQueue({ 
        compare: (a, b) => {
            if (a[0] !== b[0]) return a[0] - b[0];
            return a[1] - b[1];
        }
    });
    
    // 忙碌服务器堆：[完成时间, 下标]
    const busy = new MinPriorityQueue({ 
        compare: (a, b) => {
            if (a[0] !== b[0]) return a[0] - b[0];
            return a[1] - b[1];
        }
    });
    
    for (let i = 0; i < n; i++) {
        available.enqueue([servers[i], i]);
    }
    
    let time = 0;
    for (let i = 0; i < m; i++) {
        time = Math.max(time, i);
        
        // 将完成的服务器移回可用堆
        while (!busy.isEmpty() && busy.front()[0] <= time) {
            const [endTime, idx] = busy.dequeue();
            available.enqueue([servers[idx], idx]);
        }
        
        // 如果没有可用服务器，等待最早完成的服务器
        if (available.isEmpty()) {
            time = busy.front()[0];
            while (!busy.isEmpty() && busy.front()[0] <= time) {
                const [endTime, idx] = busy.dequeue();
                available.enqueue([servers[idx], idx]);
            }
        }
        
        // 分配任务
        const [weight, serverIdx] = available.dequeue();
        ans[i] = serverIdx;
        busy.enqueue([time + tasks[i], serverIdx]);
    }
    
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m log n)，其中 m 是任务数，n 是服务器数。每个任务最多进行 O(log n) 次堆操作
空间复杂度O(n)，需要存储所有服务器在优先队列中

相关题目