LeetCode 1606. Find Servers That Handled Most Number of Requests
原题链接
困难
作者:
孤独时代的罗永浩
,
2020-10-05 10:11:51
,
所有人可见
,
阅读 637
开两部分存储空间,用set来存当前空闲的处理器, 优先队列存储当前在工作的处理器
每次遍历到新的请求的时候先将队列中所有已经停止工作的点放入到set中,
再在set中找到需要大于等于当前点的第一个点, 如果不存在就用set的第一个点作为运行这个请求的处理器
将当前处理器和请求时间加入到优先队列中
C++ 代码
class Solution {
public:
vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> q; // time index;
vector<int> ans = vector<int>(k, 0);
set<int> hash;
for(int i = 0; i < k; i++)
hash.insert(i);
for(int i = 0; i < arrival.size(); i++)
{
int index = i % k;
int time = arrival[i];
while(q.size() && q.top().first <= time)
{
int a = q.top().second;
hash.insert(a);
q.pop();
}
if(hash.size() == 0) continue;
auto it = hash.lower_bound(index);
int newindex = 0;
if(it != hash.end())
{
newindex = *it;
hash.erase(it);
}
else
{
newindex = *hash.begin();
hash.erase(hash.begin());
}
q.push({time + load[i], newindex});
ans[newindex] ++;
}
vector<int> temp;
int res = 0;
for(int i = 0; i < ans.size(); i++)
{
if(ans[i] == res)
temp.push_back(i);
if(ans[i] > res)
{
res = ans[i];
temp.clear();
temp.push_back(i);
}
}
return temp;
}
};