题目描述

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

你正在运行一个仿真系统，在处理完所有任务后，该系统将会关闭。每台服务器只能同时处理一项任务。第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j 秒可以开始处理。处理第 j 项任务时，你需要为它分配一台 权重最小 的空闲服务器。如果存在多台相同权重的空闲服务器，请选择 下标最小 的服务器。如果一台空闲服务器在第 t 秒分配到第 j 项任务，那么在 t + tasks[j] 时它将恢复空闲状态。

如果没有空闲服务器，则必须等待，直到出现一台空闲服务器，并 尽可能早 地处理剩余任务。 如果有多项任务等待分配，则按照 下标递增 的顺序完成分配。

如果同一时刻存在多台空闲服务器，可以同时将多项任务分别分配给它们。

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

返回答案数组 ans。

样例

输入：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 秒。

输入：servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
输出：[1,4,1,4,1,3,2]
解释：事件按时间顺序如下：
- 0 秒时，第 0 项任务加入到任务队列，使用第 1 台服务器处理到 2 秒。
- 1 秒时，第 1 项任务加入到任务队列，使用第 4 台服务器处理到 2 秒。
- 2 秒时，第 1 台和第 4 台服务器空闲，第 2 项任务加入到任务队列，使用第 1 台服务器处理到 4 秒。
- 3 秒时，第 3 项任务加入到任务队列，使用第 4 台服务器处理到 7 秒。
- 4 秒时，第 1 台服务器空闲，第 4 项任务加入到任务队列，使用第 1 台服务器处理到 9 秒。
- 5 秒时，第 5 项任务加入到任务队列，使用第 3 台服务器处理到 7 秒。
- 6 秒时，第 6 项任务加入到任务队列，使用第 2 台服务器处理到 7 秒。

限制

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

算法

(模拟，堆) $O((n + m) \log n)$

1. 设置两个堆，一个存储当前正在工作的服务器，一个存储当前空闲的服务器。
2. 对于一个新任务，释放 $i$ 之前完成任务的忙碌服务器，加入到空闲服务器堆中。
3. 如果此时有空闲的服务器，则 $i$ 任务使用当前最优的空闲服务器。否则，从忙碌服务器中取出一个最早结束且最优的服务器分配给 $i$ 任务。

时间复杂度

• 均摊来看，每个任务都会使一个服务器从空闲变成忙碌，故总时间复杂为 $O((n + m) \log n)$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间存储堆和答案。

C++ 代码

struct IdleServer {
    int w, idx;
    IdleServer(int w_, int idx_) {
        w = w_; idx = idx_;
    }
    bool operator < (const IdleServer &p) const {
        if (w != p.w) return w > p.w;
        return idx > p.idx;
    }
};

struct BusyServer {
    int t, w, idx;
    BusyServer(int t_, int w_, int idx_) {
        t = t_; w = w_; idx = idx_;
    }
    bool operator < (const BusyServer &p) const {
        if (t != p.t) return t > p.t;
        if (w != p.w) return w > p.w;
        return idx > p.idx;
    }
};

class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        priority_queue<IdleServer> idle;
        priority_queue<BusyServer> busy;
        const int n = servers.size();
        const int m = tasks.size();

        for (int i = 0; i < n; i++)
            idle.push(IdleServer(servers[i], i));

        vector<int> ans(m);

        for (int i = 0; i < m; i++) {
            // 在 i 时刻之前完成任务的服务器统一释放，插入到空闲的 服务器堆中
            while (!busy.empty() && busy.top().t <= i) {
                auto s = busy.top();
                busy.pop();
                idle.push(IdleServer(servers[s.idx], s.idx));
            }

            if (!idle.empty()) {
                // i 时刻如果存在空闲的 server，则分配任务给空闲 server
                IdleServer s = idle.top();
                idle.pop();

                ans[i] = s.idx;
                busy.push(BusyServer(i + tasks[i], servers[s.idx], s.idx));
            } else {
                // i 时刻不存在空闲的服务器，则从忙碌的服务器堆中取出一个最早会结束且权重最小的
                // 分配给任务 i 后重新插入忙碌的服务器堆中
                BusyServer s = busy.top();
                busy.pop();

                ans[i] = s.idx;
                busy.push(BusyServer(s.t + tasks[i], servers[s.idx], s.idx));
            }
        }

        return ans;
    }
};