提交时间:2022-07-19 12:03:12

运行 ID: 52371

#include <bits/stdc++.h> using namespace std; const int M=1e5*5+1; inline int Read() { int x=0; char c=getchar(); for(; c<'0' || c>'9'; c=getchar()); for(; c<='9' && c>='0'; c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x; } struct Game { long long l,r; } G[M],a[M]; long long N; int Cmp(const Game&x,const Game&y) { return x.l<=y.l; } int main() { N=Read(); for(int i=1; i<=N; i++) G[i].l=Read(),G[i].r=Read(); sort(G+1,G+N+1,Cmp); long long Max=0,t=1; for(int i=N; i>0; i--) { t=1; a[1].l=G[i].l,a[1].r=G[i].r; for(int j=i-1; j>0; j--) { if(G[j].l<=a[t].l&&G[j].r>=a[t].r) { a[++t].l=G[j].l,a[t].r=G[j].r; } } if(Max<t) Max=t; for(int j=1; j<=N; j++) a[j].l=0,a[j].r=0; } cout<<Max<<endl; return 0; }