LeetCode-1606. 找到处理最多请求的服务器、C++中优先队列的使用

你有 k 个服务器，编号为 0 到 k-1 ，它们可以同时处理多个请求组。每个服务器有无穷的计算能力但是 不能同时处理超过一个请求 。请求分配到服务器的规则如下：
第 i （序号从 0 开始）个请求到达。
如果所有服务器都已被占据，那么该请求被舍弃（完全不处理）。
如果第 (i % k) 个服务器空闲，那么对应服务器会处理该请求。
否则，将请求安排给下一个空闲的服务器（服务器构成一个环，必要的话可能从第 0 个服务器开始继续找下一个空闲的服务器）。比方说，如果第 i 个服务器在忙，那么会查看第 (i+1) 个服务器，第 (i+2) 个服务器等等。
给你一个 严格递增 的正整数数组 arrival ，表示第 i 个任务的到达时间，和另一个数组 load ，其中 load[i] 表示第 i 个请求的工作量（也就是服务器完成它所需要的时间）。你的任务是找到 最繁忙的服务器 。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。
请你返回包含所有 最繁忙服务器 序号的列表，你可以以任意顺序返回这个列表
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-servers-that-handled-most-number-of-requests

题目分析

综合使用 STL 中的一些数据结构及算法来解决本题，主要涉及的知识点如下：
①．set：有序集合，元素不重复，默认升序
②．pair：包含 first 和 second 两个元素的结构体，排序先比较 first、再比较 second
③．priority_queue：优先队列，默认降序排序，即最大值排第一个
④．lower_bound：采用二分查找，查找第一个大于等于目标值的元素，返回其迭代器
⑤．max_element：返回指定范围中最大值的迭代器

详细解题过程见代码及注释

代码示例

class Solution {
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {

        set<int> canUseServer;//当前可用的服务器列表，按编号排序
        for( int i = 0;i < k;++i ) canUseServer.insert(i);//初始全部服务器可用

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> workServer;
        //工作中的服务器，按工作结束时间排序 ：<工作结束时间,服务器编号>

        vector<int> requests(k);//每个服务器处理的任务数

        auto doTask = [&](int taskNum){//处理第 taskNum 项任务
            //查找在任务到来之前以及结束工作的服务器    
            while (!workServer.empty() && workServer.top().first <= arrival[taskNum]) {
                canUseServer.insert(workServer.top().second);//加入到可用服务器
                workServer.pop();//工作服务器中移除
            }
            if( canUseServer.empty()) return;//没有可用服务器，跳过该任务

            auto iter = canUseServer.lower_bound(taskNum % k); //查找对应服务器：第一个 >= taskNum % k
            if (iter == canUseServer.end()) iter = canUseServer.begin();//没找到则返回开头一个可用的服务器
            requests[*iter]++;//对应服务器处理任务数+1

            workServer.emplace(arrival[taskNum] + load[taskNum], *iter);//添加到工作队列
            canUseServer.erase(iter);//可用服务器中删除

        };

        for (int i = 0; i < arrival.size(); i++) 
        {    
            doTask(i);//执行每一项任务
        }

        int maxCount = *max_element(requests.begin(), requests.end());//找到最大的执行任务数
        vector<int> result;
        for (int i = 0; i < k; i++) {
            if (requests[i] == maxCount) {//找到所有等于最大任务数的服务器
                result.push_back(i);
            }
        }
        return result;


    }
    
};