1882. 使用服务器处理任务(力扣5.30周赛题目三)

题目:
给你两个 下标从 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​​​​ 。

使用的方法:优先队列

我们使用两个优先队列分别存储工作中的服务器以及空闲的服务器:

优先队列busy 存储工作中的服务器,每一台服务器用二元组 (t,idx) 表示,其中 tt 为该服务器结束工作的时间,idx 为该服务器的编号。优先队列的队首服务器满足 tt 最小,并且在 tt 相同的情况下,idx 最小。

优先队列 idle 存储空闲的服务器,每一台服务器用二元组(w,idx) 表示,其中 ww 为该服务器的 weight,idx 为该服务器的编号。优先队列的队首服务器满足 ww 最小,并且在 ww 相同的情况下,idx 最小。

这样设计的好处在于:

随着时间的增加,我们可以依次从优先队列 busy 中取出已经工作完成(即时间大于等于 tt)的服务器;

当我们需要给任务安排服务器时,我们可以依次从优先队列idle 中取出可用的服务器。

算法的流程:

在初始时,我们将所有服务器放入优先队列idle 中,并使用一个时间戳变量 ts 记录当前的时间,其初始值为 00;

随后我们遍历每一个任务:

由于第 ii 个任务必须在时间 ii 时才可以开始,因此需要将 ts 置为其与 ii 的较大值;

我们需要将优先队列 busy 中满足t≤ts 的服务器依次取出并放入优先队列 idle;

如果此时优先队列idle 中没有服务器,说明我们需要等一台服务器完成任务,因此可以将 ts 置为优先队列 busy 的队首服务器的任务完成时间 tt,并再次执行上一步;

此时我们就可以给第 ii 个任务安排服务器了,即为优先队列idle 的队首服务器,将其取出并放入优先队列busy。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/process-tasks-using-servers

代码如下,需要注意的几点下面都mark了。

class Solution {
private:
    using pii=pair<int,int>;//简写
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {

        priority_queue<pii,vector<pii>,greater<pii>> idle;
        priority_queue<pii,vector<pii>,greater<pii>> busy;

        int m=servers.size();int n=tasks.size();
        for(int i=0;i<m;i++)
        {
            idle.emplace(servers[i],i);//初始化idle
        }

        int ts=0;//ts要在内部函数前定义
        auto release=[&]()//内部函数,注意auto的运用
        {
            while(!busy.empty()&&busy.top().first<=ts)
            {
                auto&& [_,idx]=busy.top();
                idle.emplace(servers[idx],idx);
                busy.pop();
            }
        };

        vector<int> ans;
        for(int i=0;i<n;i++)
        {
            ts=max(ts,i);//1
            release();//2

            if(idle.empty())//3
            {
                ts=busy.top().first;
                release();
            }

            //4
            auto&& [_,idx]=idle.top();
            busy.emplace(ts+tasks[i],idx);  

            ans.push_back(idx); idle.pop();//这两句不能交换顺序,auto得到的idx具有实时性
        }
       return ans;
    }
};
上一篇:如何确定Flink反压的根源?How to identify the source of backpressure?


下一篇:Docker - 解决在容器内删除和主机映射的目录而报错 rm: cannot remove 'webapps': Device or resource busy 的问题