题目描述
blablabla
样例
blablabla
算法1
C++ 代码
/**
* 按左端点排序
* i, j是当前区间的左右端点,cnt是区间个数
* 枚举每个区间z,有三种情况:
* 1.完全包含,跳过
* 2.部分包含,j = z.j
* 3.完全不包含 cnt += 1, i = z.i, j = z.j
*
**/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
PII p[N];
int cmp(PII p1, PII p2){
return p1.first < p2.first;
}
int main(){
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &p[i].first, &p[i].second);
sort(p + 1, p + n + 1, cmp);
int cnt = 1;
int i = p[1].first, j = p[1].second;
for (int k = 2; k <= n; k ++ ){
int zi = p[k].first, zj = p[k].second;
//情况1
if(zi >= i && zj <= j) continue;
//情况3
else if(zi > j) {
cnt += 1;
i = zi;
j = zj;
}else {
//情况2
j = zj;
}
}
printf("%d", cnt);
}