【OJ】贪心法 (区间问题——木棒)1129/

题目链接：点击打开链接

/*

贪心法 (区间问题——木棒)1129/

*/

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=5010;
typedef pair<int,int> P;
pair<int,int>itv[maxn];
int ok[maxn];
bool comp( P  a,const P & b){     //const &
	if (a.second==b.second)return a.first<b.first;//
//	else return false;
	return a.second<b.second;
}
int main(){
///	freopen("贪心（区间）.txt","r",stdin);
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		memset(ok,0,sizeof(ok));
		for(int i=0;i<n;i++){
			cin>>itv[i].first>>itv[i].second;///
		}
//		sort(itv,itv+n);//sort first defaultly.
		sort(itv,itv+n,comp);//can sort first or second
	//	for(int j=0;j<n;j++)//sort the first of itv;
		//	cout<<itv[j].first<<" "<<itv[j].second<<endl; 
		int ll,ans=0,count=0;
		for(int i=0;i<n;i++){		
			for(int k=0;k<n;k++)
				if(!ok[k]){
					ll=itv[k].first;
					ok[k]=1;
					ans++;count++;break;				
				}		
			for(int j=0;j<n;j++)
				if(!ok[j]&&ll<=itv[j].first){
					ok[j]=1;
					ll=itv[j].first;
					count++;
				}
			if(count==n)break;	
		}
		cout<<ans<<endl;		
	}
	return 0;
}