力扣2402.会议室 III
-
双堆模拟
- 一个堆存未占用的会议室编号
- 一个堆存已占用的结束时间和编号
-
class Solution {public:int mostBooked(int n, vector<vector<int>>& meetings) {int cnt[n];memset(cnt,0,sizeof(cnt));priority_queue<int,vector<int>,greater<>> idle;for(int i=0;i<n;i++) idle.push(i);priority_queue<pair<long,int>,vector<pair<long,int>>,greater<>> using_;//按照开始时间排序sort(meetings.begin(),meetings.end(),[](auto &a,auto &b){return a[0] <b[0];});for(auto &m:meetings){long st = m[0],end = m[1],id;//已经到了结束时间，弹出去while(!using_.empty() && using_.top().first <= st){idle.push(using_.top().second);using_.pop();}//没有空会议室了if(idle.empty()){auto [e,i] = using_.top();using_.pop();//结束时间 + 等待时间end += e - st;id = i;}//有空会议室else{id = idle.top();idle.pop();}cnt[id] ++;using_.emplace(end,id);}int ans = 0;//取最大的cntfor(int i=0;i<n;i++)if(cnt[i] > cnt[ans])ans = i;return ans;}};
