Time Limits: 1000 ms Memory Limits: 65536 KB

Description

Alice收到一些很特别的生日礼物:区间。即使很无聊,Alice还是能想出关于区间的很多游戏,其中一个是,Alice从中选出最长的不同区间的序列,其中满足每个区间必须在礼物中,另序列中每个区间必须包含下一个区间。
  编程计算最长序列的长度。

Input

输入文件第一行包含一个整数N(1<=N<=100000),表示区间的个数。
  接下来N行,每行两个整数A和B描述一个区间(1<=A<=B<=1000000)。

Output

输出满足条件的序列的最大长度。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
输入1:
3
3 4
2 5
1 6

输入2:
5
10 30
20 40
30 50
10 60
30 40

输入3:
6
1 4
1 5
1 6
1 7
2 5
3 5

Sample Output

1
2
3
4
5
6
7
8
输出1:
3

输出2:
3

输出3:
5

Data Constraint

Hint

【样例解释】
  例3中可以找到长度为5的区间序列是:[1,7]、[1,6]、[1,5]、[2,5]、[3,5]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int INF=2e9;
struct node {
int l,r;
}a[MAXN];
int n;
int s[MAXN],top;
bool cmp (node a,node b){
if (a.l==b.l) return a.r<b.r;
return a.l>b.l;
}
int main(){
cin>>n;
for (int i=1;i<=n;i++){
scanf ("%d%d",&a[i].l,&a[i].r);
}
sort (a+1,a+n+1,cmp);
for (int i=1;i<=n;i++){
int t=a[i].r;
if (t>=s[top]) s[++top]=t;
else {
int l=1,r=top,mid;
while (l<=r){
mid=(l+r)/2;
if (s[mid]<=t) l=mid+1;
else r=mid-1;
}
s[l]=t;
}
}
cout<<top<<endl;
return 0;
}