且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

【OJ】贪心——区间问题 hzu.acmclub.com 1126看电视

更新时间:2021-08-09 11:54:20

题目链接:<a target=_blank href="http://hzu.acmclub.com/index.php?app=problem_title&id=538&problem_id=1126">点击打开链接</a>

/*
贪心——区间问题 hzu.acmclub.com 1126看电视 
*/
#include<iostream>
#include<algorithm>
using namespace std;
//typedef pair<int,int> P;  /////////////用pair<int,int>
//P tv[101];
//bool comp(P a,const P &b){
////	if(a.second<b.second)return true;//1种 
////	else return false;               //1
////	return a.second<b.second; //2
//	if(a.second!=b.second)return a.second<b.second;//3
//	return a.first<b.first;                        //3
//}
struct TV{                 ////////////用struct 
	int ai,ei;
}tv[101];
bool comp(TV a,TV b){
//	return a.ei <b.ei ;
	if(a.ei!=b.ei )return a.ei<b.ei;
	return a.ai<b.ai;
}
int main(){
//	freopen("贪心(区间1126看电视.txt","r",stdin);
	int n;
	while(cin>>n&&n){
		for(int i=0;i<n;i++){
//			cin>>tv[i].first>>tv[i].second;//用pair<int,int> 
			cin>>tv[i].ai>>tv[i].ei;       //用struct 
		}
		sort(tv,tv+n,comp); 
		int ans=0,t=0;
//		for(int j=0;j<n;j++){   //用pair<int,int> 
//			if(t<=tv[j].first){
//				ans++;
//				t=tv[j].second;
//			}
//		}
		for(int j=0;j<n;j++){   //用struct 
			if(t<=tv[j].ai){
				ans++;
				t=tv[j].ei;
			}
		}
		cout<<ans<<endl;		
	}
	return 0;
}