243 周赛5774 使用服务器处理任务（双优先队列）

题目链接：https://leetcode-cn.com/problems/process-tasks-using-servers/

题目描述

给你两个整数数组，一个数组servers代表服务器的权重，另一个数组tasks表示完成第i个任务所需要的时间，只能按数组的下标依次安排任务，第 0 项任务在第 0 秒可以开始处理，相应地，第 j 项任务在第 j 秒可以开始处理，在处理第t个任务时，需要给他分配一台权值最小的空闲的服务器，如果权值相同则分配一台下标最小的那台，在服务器完成任务时从忙碌转为空闲状态，问每一个任务用的是哪一台服务器。

思路

用两个优先队列去维护空闲和忙碌的服务器
code：

class Solution {
   public:
    struct av {
        int id, ti, pri;//下标，服务器结束工作的时间，权值
        bool operator<(const av& t) const {
            if (pri != t.pri)
                return pri > t.pri;
            else
                return id > t.id;
        }
        //依照题目表述调整优先级：你需要为它分配一台 权重最小 的空闲服务器。如果存在多台相同权重的空闲服务器，请选择 下标最小 的服务器
    };
    struct ba {
        int id, ti, pri;
        bool operator<(const ba& t) const { return ti > t.ti; }
        //结束时间快的优先级高
    };
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        priority_queue<av> ava;//可用服务器
        priority_queue<ba> bac;//忙碌服务器
        vector<int> ans;
        for (int i = 0; i < servers.size(); i++) ava.push({i, 0, servers[i]});
        for (int i = 0; i < tasks.size(); i++) {
            //如果忙碌的服务器的结束时间<当前时间，说明这个服务器已经闲置
            while (!bac.empty() && bac.top().ti <= i) {
                ava.push({bac.top().id, bac.top().ti, bac.top().pri});
                bac.pop();
            }
            if (ava.empty()) {//考虑当前可用为0的情况（特殊情况）
                ba bk = bac.top();
                while (!bac.empty() && bac.top().ti <= bk.ti) {
                    ava.push({bac.top().id, bac.top().ti, bac.top().pri});
                    bac.pop();
                }
            }
            //可用到忙碌状态的转化
            av an = ava.top();
            ava.pop();
            //进队的时间会大于等于i
            if (an.ti < i) an.ti = i;
            an.ti += tasks[i];
            ans.push_back(an.id);
            bac.push({an.id, an.ti, an.pri});
        }
        return ans;
    }
};