前言
本菜鸡第一次写题解,还望各位大佬轻点喷,如果内容对你有帮助,那就点个赞吧
思路
-
将左端点从小到大排序
-
从前往后枚举每个区间,用一个小根堆来记录所有组里面的区间的右端点的最大值
如果这个区间的左端点比 (所有组记录的最大值) 的最小值还小,说明区间必然相交,于是需要新开一个组,并存进右端点
如果不是,则加到最小值后面,并更新该组存的最大值
·为什么是最小值?
· 因为要让所有组数(最终答案)尽可能地小,就要让每个组装得多一些,高效利用
C++ 代码
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int main(){
int n;
cin >> n;
vector<pair<int, int>> tmp;
for(int i = 0; i < n; i++){
pair<int, int> p;
cin >> p.first >> p.second;
tmp.push_back(p);
}
sort(tmp.begin(), tmp.end());
priority_queue<int, vector<int>, greater<int>> heap;
for(int i = 0; i < n; i++){
if(!heap.size() || tmp[i].first <= heap.top()){
heap.push(tmp[i].second);
}else{
heap.pop();
heap.push(tmp[i].second);
}
}
cout << heap.size();
return 0;
}
😭😭😭😭