题目描述

官方描述(中文)
2022/03/11每日一题

题解

根据官方提供的题解思路编写代码。
官方题解

代码

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

	//存储空闲服务器序列号
        std::set<int>avliable;

	//优先队列,存储任务结束时间-服务器序列的键值对,
	//跟进结束时间由小到大排列
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> busy;
        int maxResq{0};

        for(int i = 0; i<k; ++i)avliable.insert(i);
        for(int i = 0; i< arrival.size(); ++i)
        {
	    //遍历繁忙服务器列表,将所有在此次请求到来之前执行结束的
	    //服务器放入空闲列表
            while(busy.size() && busy.top().first <= arrival[i])
            {
                avliable.insert(busy.top().second);
                busy.pop();
            }
	    
	    //没有空闲的服务器,丢弃请求
            if(avliable.empty())
            {
                continue;
            }
	     
            //寻找要执行此任务的服务器,先获取第一个大于等于i%k的服务器。
            //如果没有找到,就是用列表内的第一个		 
            auto iter = avliable.lower_bound(i%k);
            if(iter == avliable.end())
            {
                iter  = avliable.begin();
            }
	   
            //将执行此请求的服务器放入繁忙服务器队列
            busy.push({arrival[i]+load[i], *iter});
            maxResq = max(maxResq, ++resquests[*iter]);

            avliable.erase(iter);
        }
        
        std::vector<int>res;
        for(int i= 0; i<k; ++i)
        {
            if(resquests[i] == maxResq)
            {
                res.push_back(i);
            }
        }

        return res;
    }
};

Q.E.D.