当前位置:首页 > 编程笔记 > 正文
已解决

LeetCode 2402.会议室III ----堆+模拟

来自网友在路上 167867提问 提问时间:2023-11-01 00:23:39阅读次数: 67

最佳答案 问答题库678位专家为你答疑解惑

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;}
};

查看全文

99%的人还看了

猜你感兴趣

版权申明

本文"LeetCode 2402.会议室III ----堆+模拟":http://eshow365.cn/6-29127-0.html 内容来自互联网,请自行判断内容的正确性。如有侵权请联系我们,立即删除!