Problem1389--程序员PIPI II

1389: 程序员PIPI II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 548  Solved: 128
[Submit] [Status] [Web Board] [Creator:]

Description

程序员PIPI有许多电脑,他每天要用这些电脑处理许多个进程,每个进程有开始于第S天,结束于第 T天 (即进程的执行区间为[S,T] ),这些进程需要一些电脑来进行处理。
每一个进程只需要在 S≤d≤T的任意一天d进行处理即可 , 值得注意的是,PIPI的电脑每天只能处理一个进程。现在有n个进程到了PIPI手上,PIPI想知道他最多能够处理多少个进程?

Input

输入包含多组测试用例。
对于每组样例,第一行包含一个正整数 n (n<=1e5),代表进程的数目。
接下来n行每行输入进程的开始时间 S 和结束时间 T, (0<=S<=T<=1e5)。

Output

对于每组样例,输出PIPI最多可以处理多少个进程。

Sample Input

3
1 2
2 3
3 4
4
1 2
2 3
3 4
1 2
5
1 4
4 4
2 2
3 4
1 1

Sample Output

3
4
4

HINT

对于样例1: 可以在第一天处理[1,2] 第二天处理[2,3] 第三天处理[3,4]
对于样例2: 可以在第一天处理[1,2] 第二天处理[1,2] 第三天处理[2,3] 第四天处理[3,4]

Source/Category

中等