首先排个序,然后找一次0花费,然后再找一次0花费,然后再找一次0花费,然后再找一次0花费.........
最后看找了几次,+1就是答案
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
struct node
{
int l,w;
friend istream & operator >>(istream &is,node &a)
{
is>>a.l>>a.w;
return is;
}
};
bool cmp(node a,node b)
{
return a.l!=b.l?a.l<b.l:a.w<b.w;
}
bool operator <=(node a,node b)
{
return a.l<=b.l&&a.w<=b.w;
}
int main()
{
//freopen("in","r",stdin);
node box[5010];
bool vis[5010];
int ans,i,n,j,T;
node p;
cin>>T;
while(T--)
{
cin>>n;
for(i=0;i<n;i++)
cin>>box[i];
ans=1;
memset(vis,0,sizeof(vis));
sort(box,box+n,cmp);
p=box[0];
for(i=0;i<n;i++)
{
if(vis[i])
continue;
if(!(p<=box[i]))
ans++;
p=box[i];
for(j=i+1;j<n;j++)
{
if(vis[j])
continue;
if(p<=box[j])
{
p=box[j];
vis[j]=1;
}
}
}
cout<<ans<<endl;
}
return 0;
}