AcWing 906. 区间分组
原题链接
简单
作者:
芳_8
,
2023-11-21 21:07:44
,
所有人可见
,
阅读 38
算法1
(暴力枚举) $O(n^2)$
时间复杂度&o(n)&
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e6+5;
int n;
struct ge{//结构体
int a, b;
bool operator< (const ge &W)const{
return a < W.a;
}
};
ge r[N];
int main(){
cin >> n;
for (int i = 0; i < n; i ++ ){
int a, b;
cin >> a >> b;//输入
r[i] = {a, b};
}
sort(r, r + n);
priority_queue<int, vector<int>, greater<int>> h;//嵌套
for (int i = 0; i < n; i ++ ){
auto s = r[i];
if (h.empty() || h.top() >= s.a) h.push(r[i].b);//贪心算法
else{
h.pop();
h.push(r[i].b);
}
}
cout << h.size();
return 0;
}