习题 8-15 笔记本（Laptop, ACM/ICPC Daejeon 2012, UVa1617）

原题链接：https://vjudge.net/problem/UVA-1617
分类：贪心法
备注：区间相关问题

#include
using namespace std;
const int maxn=1e5+5;
int t,n;
struct node{int r,d;bool operator < (const node& rhs)const{return d<rhs.d||(d==rhs.d&&r<rhs.r);}
}a[maxn];
int main(void){//freopen("in.txt","r",stdin);scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d%d",&a[i].r,&a[i].d);sort(a,a+n);int befR=a[0].d,ans=0;for(int i=1;i<n;i++){if(a[i].r>befR){ans++; befR=a[i].d;}else{if(a[i].d>befR)befR++;}}printf("%d\n",ans);}return 0;
}