用普通区间思路没法做,但是涉及到区间贪心问题;
优先选择结束时早的,就可以腾出来时间给其他会议;
因此可以按照时间轴遍历,把所有会议加入到时间轴中;
pq保留所有已开始会议的结束时间;
每遍历一个时间点,做两件事:
- 删除所有的已经超时会议;
- 选取一个最早结束的会议参加,参加会议+1;
pq相当于保存已开始但是未结束的会议;
具体代码:class Solution {
public:
int maxEvents(vector>& events) {
const int size=1e5+5;
vector>time(size);
int ret=0;
priority_queue, greater<>>pq;
int index=0;
for(auto& vec:events){
time[vec[0]].push_back(index);
index++;
}
for(int i=0;i
for(auto& ele:time[i]){
pq.push(events[ele][1]);
//加入终止时间;
}
while(!pq.empty()&&pq.top()
pq.pop();
//排除掉已经结束的会议;
}
if(!pq.empty()){
ret++;
pq.pop();
}
}
return ret;
}
};



