题目描述
- 最大不相交区间数量
给定 N
个闭区间 [ai,bi]
,请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。
输出可选取区间的最大数量。
样例
cin>>
3
-1 1
2 4
3 5
cout<<
2
算法1
(贪心) $O(n^2)$
要保证在同一个区间内,任意两条线段有交集。
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node{
int left, right;
}range[N];
bool cmp(node x, node y){
return x.left < y.left;
}
int main(void){
int n, sum = 1;
cin >> n;
for(int i = 0; i < n; i++) cin >> range[i].left >> range[i].right;
sort(range, range + n, cmp);
int tmp = range[0].right;
for(int i = 1; i < n; i++){
if(range[i].left > tmp){
sum++;
tmp = range[i].right;
}
else tmp = min(tmp, range[i].right);
}
cout << sum << endl;
return 0;
}