)
2402: 会议室Ⅲ
思路：双堆模拟priority_queue
按照时间顺序模拟开会过程。
对于会议 [start,end)，我们需要知道：
- 在 start 时刻空闲的会议室中，编号最小的会议室。可以用一个最小堆 idle 维护空闲会议室的编号。
- 如果没有空闲的会议室呢？我们需要找最早结束的会议室。可以用一个最小堆 inUse 维护使用中的会议室的结束时间和编号。
这两类会议室是互补关系，伴随着会议的开始和结束，会议室在这两类中来回倒：
- 首先，从 inUse 中去掉结束时间小于等于 start的所有会议室，将其编号添加到 idle 中。（使用结束）
然后分类讨论：
如果此时有空闲的会议室，那么从 idle 中弹出编号最小的会议室，和 end 一起，添加到 inUse 中。
否则，从 inUse 中弹出一个最早结束的会议室（若有多个同时结束，弹出编号最小的会议室），顺延会议的结束时间为 end+e−start。
在上述模拟的过程中，每使用一个编号为 i 的会议室，就把 i 的出现次数加一。返回举办最多次会议的房间编号。如果存在多个房间满足此条件，则返回编号最小的房间。
注意题目保证所有会议的开始时间互不相同。
class Solution { public: int mostBooked(int n, vector<vector<int>>& meetings) { ranges::sort(meetings,{},[](auto& m){return m[0];}); //小根堆（堆顶最小） priority_queue<int,vector<int>,greater<>> idle; //会议室编号 for(int i=0;i<n;i++) idle.push(i); //{结束时间，会议室编号} priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> inUse; vector<int> cnt(n); //使用次数 for(auto& m:meetings){ long long start=m[0],end=m[1]; //在start时刻空出来的会议室 while(!inUse.empty() && inUse.top().first<=start){ //使用结束 idle.push(inUse.top().second); inUse.pop(); } int i; if(!idle.empty()){ //有空闲的会议室 i=idle.top(); idle.pop(); } else{ //没有空闲的会议室 auto[e,room]=inUse.top(); //弹出最早结束的会议室（若有多个同时结束，弹出编号最小的会议室） i=room; inUse.pop(); end+=e-start; //延期会议的持续时间和原会议持续时间相同 } inUse.emplace(end,i); cnt[i]++; } int ans=0; for(int i=0;i<n;i++){ if(cnt[i]>cnt[ans]) ans=i; } return ans; } };
