LeetCode 5774. 使用服务器处理任务
原题链接
中等
作者:
ITNXD
,
2021-05-31 19:55:08
,
所有人可见
,
阅读 296
详细请查看注释内容
参考代码:
class Solution {
/*
使用两个堆维护两个集合,一个处于忙碌状态的,一个处于空闲状态的即可!
具体看下方注释内容!
*/
public:
// 忙碌(时间小 权重小 下标小)
struct Node1{
int w, id, tm;
bool operator< (const Node1& t) const{
// 按时间 权重 id排序(堆默认为大根堆,反着写即可变为小根堆)
if(tm != t.tm) return tm > t.tm;
if(w != t.w) return w > t.w;
return id > t.id;
}
};
// 空闲(权重小,下标小)
struct Node2{
int w, id, tm;
bool operator< (const Node2& t) const{
// 按权重 id排序(堆默认为大根堆,反着写即可变为小根堆)
if(w != t.w) return w > t.w;
return id > t.id;
}
};
vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
priority_queue<Node1> heap1; // 忙碌
priority_queue<Node2> heap2; // 空闲
vector<int> res;
// 初始时都是空闲状态
for(int i = 0; i < servers.size(); i ++) heap2.push({servers[i], i, 0});
// 遍历去处理每个任务
for(int i = 0; i < tasks.size(); i ++){
// 先将所有先前处于忙碌状态当前处于空闲状态的从heap1转移到heap2
while(heap1.size() && heap1.top().tm <= i){
auto t = heap1.top(); heap1.pop();
heap2.push({t.w, t.id, t.tm});
}
// 若有空闲服务器
if(heap2.size()){
auto t = heap2.top(); heap2.pop();
// 时间为当前时间i + 需要运行时间tasks[i]
heap1.push({t.w, t.id, i + tasks[i]});
res.push_back(t.id);
}else{ // 若无空闲状态服务器
auto t = heap1.top(); heap1.pop();
// 时间为忙碌状态结束时间 t.tm + 需要运行时间tasks[i]
heap1.push({t.w, t.id, t.tm + tasks[i]});
res.push_back(t.id);
}
}
return res;
}
};