51Nod --1133 不重叠的线段

51Nod --1133 不重叠的线段

X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。

 

例如：[1 5][2 3][3 6]，可以选[2 3][3 6]，这2条线段互不重叠。

Input

第1行：1个数N，线段的数量(2 <= N <= 10000)
第2 - N + 1行：每行2个数，线段的起点和终点(-10^9 <= S,E <= 10^9)

Output

输出最多可以选择的线段数量。

Input示例

3
1 5
2 3
3 6

Output示例

2

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
using namespace std; 
const int MAXN = 10005; 

struct Node{
	int lf, rg; 
}nd[MAXN]; 

int n; 

int cmp(const void *a, const void *b){
	Node *aa = (Node *)a; 
	Node *bb = (Node *)b; 
	if( aa->lf == bb->lf ){
		return aa->rg - bb->rg; 
	}else {
		return aa->lf - bb->lf; 
	}
}
int main(){
	int cnt, left_val, right_val; 
	while(scanf("%d", &n) != EOF){
		for(int i=0; i<n; ++i){
			scanf("%d %d", &nd[i].lf, &nd[i].rg); 
		}
		qsort(nd, n, sizeof(nd[0]), cmp); 
		left_val = nd[0].lf; 
		right_val = nd[0].rg; 
		cnt = 1;  
		for(int i=1; i<n; ++i){
			if(right_val <= nd[i].lf){
				cnt++; 
				right_val = nd[i].rg; 
				left_val = nd[i].lf; 
			}else{
				right_val = min(right_val, nd[i].rg); 
			}
		}
		printf("%d
", cnt );
	}
	return 0; 
}