1064: 蓄栏保留问题

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：947 Solved：211

Description

农场有N头牛，每头牛会在一个特定的时间区间[A, B]（包括A和B）在畜栏里挤奶，且一个畜栏里同时只能有一头牛在挤奶。现在农场主希望知道最少几个畜栏能满足上述要求。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

输入的第一行包含一个整数N(1 ≤ N ≤ 50, 000)，表示有N牛头；接下来N行每行包含两个数，分别表示这头牛的挤奶时间[Ai, Bi](1 ≤ A≤ B ≤ 1, 000, 000)。

Output

输出的第一行包含一个整数，表示最少需要的畜栏数；

Sample Input Copy 

5
1 10
2 4
3 6
5 8
4 7

Sample Output Copy 

4

Source/Category