南郵OJ 1269区間交差問題

区間交差問題
時間制限(通常/Java):
1000 MS/3000 MS運行メモリ制限:65536 KByte総提出:99テスト合格:7
試合の説明
所与のx軸上のn個の閉区間.できるだけ少ない閉区間を除いて、残りの閉区間が交差しないようにします.
n個の閉区間を与え,プログラミングにより除去された最小閉区間数を計算した.
入力
1行目は正の整数nであり、閉区間数を表す.次のn行では,各行に2つの整数があり,それぞれ閉区間の2つの端点を表す.
しゅつりょく
算出された最小閉区間数を出力する.
サンプル入力
3 10 20 10 15 20 15
サンプル出力
2
ヒント
undefined
テーマソース
NUAA

#include<iostream>
#include<algorithm>
using namespace std;

struct seg{
	int l,r;
};

bool operator<(const seg &s1, const seg &s2){
	return s1.r<s2.r;
}

int main(){
//	freopen("test.txt","r",stdin);
	int n,i,j,count,l,r;
	scanf("%d",&n);
	seg *s = new seg[n];
	for(i=0;i<n;i++){
		scanf("%d%d",&l,&r);
		if(l<r){
			s[i].l=l;
			s[i].r=r;
		}else{
			s[i].l=r;
			s[i].r=l;
		}
	}
	sort(s,s+n);
	i=j=count=0;
	while(i<n){
		count++;
		while(j<n && s[j].l<=s[i].r){
			j++;
		}
		i = j;
	}
	printf("%d
",n-count);
}