题目描述
905.区间选点
给定 N
个闭区间 [ai,bi]
,请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
样例
cin>>
3
-1 1
2 4
3 5
cout<<
2
算法1
(贪心) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct node{
int left, right;
}range[N];
bool cmp(node x, node y){
return x.right < y.right;
}
int main(void){
int n, tmp = -2e9, sum = 0;
cin >> n;
for(int i = 0; i < n; i++) cin >> range[i].left >> range[i].right;
sort(range, range + n, cmp);
for(int i = 0; i < n; i++){
if(tmp < range[i].left){
sum++;
tmp = range[i].right;
}
}
cout << sum << endl;
return 0;
}