5e5 的st与ed 容易看出来是用堆来写的一道题目,一开始我只用了一个堆,出现了问题
问题就是当我们当前这个会议有多个可以选择的会议室可以选择的时候不一定选择那个最先结束的会议室而是应该选择可以选择的那些里面编号最小的那一个,因此我们应该加一个步骤,先把已经结束的可以选择的会议室先挑出来按照编号排序,如果可以选先这么选不能选的话我们再选结束时间最早的一个就可以了,比较丑的一个模拟 调试的过程中还是很锻炼人的
最后千万不要忘了开longlong
using ll = long long;
typedef pair<ll,ll>PII;
const int N = 110;
priority_queue<PII,vector<PII>,greater<PII>>heap;
vector<PII>vec;
int cnt[N];
class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
vec.clear();
int m = meetings.size();
memset(cnt,0,sizeof cnt);
while(heap.size())heap.pop();
for(auto&t:meetings)
vec.push_back({t[0],t[1]});
sort(vec.begin(),vec.end());
for(int i=0;i<n;i++)heap.push({-1,i});
for(int i = 0;i<m;i++){
ll xuyao = vec[i].first;
priority_queue<PII,vector<PII>,greater<PII>>heap1;
while(heap.size()){
auto t = heap.top();
if(xuyao>t.first){
heap1.push({t.second,t.first});
heap.pop();
}
else break;
}
if(heap1.size()){
auto t = heap1.top();
cnt[t.first]++;
heap.push({vec[i].second-1,t.first});
heap1.pop();
}else{
auto t = heap.top();
ll jieshu = t.first;
cnt[t.second]++;
heap.pop();
heap.push({jieshu+vec[i].second-vec[i].first,t.second});
}
while(heap1.size()){
auto t = heap1.top();
heap1.pop();
heap.push({t.second,t.first});
}
}
ll ans = 0,idx=0;
for(int i=0;i<n;i++){
if(cnt[i]>ans){
ans = cnt[i];
idx= i;
}
}
return idx;
return 0;
}
};