问题描述
数轴上有n个开区间（ai，bi），尽量选择多个区间，是的这些区间两两之间没有共同点。
输入格式
第一行的数字代表有几个区间，如果为0，则退出
后面n行每一行都是一个开区间，用空格分隔
输出格式
输出最多有几个开区间
样例
输入
4
1 3
2 4
3 5
6 7输出
3
C++实现
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
struct Interval {
int x, y;
}I[maxn];
bool cmp(Interval a, Interval b) {
if(a.x != b.x)
return a.x > b.x;
else
return a.y < b.y;
}
int main() {
int n;
while(scanf("%d", &n), n != 0) {
for(int i = 0; i < n; i++) {
scanf("%d%d", &I[i].x, &I[i].y);
}
sort(I, I + n, cmp);
int ans = 1, lastx = I[0].x;
for(int i = 1; i < n; i++) {
if(I[i].y <= lastx) {
ans++;
lastx = I[i].x;
}
}
printf("%d\n", ans);
}
return 0;
}
