题目描述
908.最大不相交区间数量
样例
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
贪心
时间复杂度 o(n)
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 100010;
int n;
//储区间
struct Range{
int l;
int r;
//重载<
bool operator < (const Range &w) const{
return r < w.r;
}
}range[N];
int main(){
cin >> n;
for(int i = 0; i < n; i) cin >> range[i].l >> range[i].r;
//区间右端点排序
sort(range, range + n);
//从第2个区间计数,用ed维护区间
int res = 1;
int ed = range[0].r;
for(int i = 1; i < n; i){
if(ed < range[i].l){
res++;
ed = range[i].r;
}
}
cout << res;
return 0;
}