4665: bzoj1651专用牛棚

Memory Limit：128 MB Time Limit：1 S
Judge Style：Text Compare Creator：
Submit：61 Solved：28

Description

有N(1 <= N <= 50,000)只挑剔的奶牛，他们非常挑剔，每只牛只能在某个精确的时间间隔 A..B (1 <= A <= B <= 1,000,000) 内挤奶，其中包括时间 A 和 B。显然，FJ须创建一个预订系统来确定每头奶牛的挤奶时间可以分配到哪个专用牛棚。当然，没有一头奶牛会与其他奶牛分享如此私密的时刻。帮助 FJ 确定：  牛舍中所需的最少专用牛棚数量， 随着时间的推移将奶牛分配到这些专用牛棚，以便每头奶牛可以有自己的挤奶时间 。

Input

第 1 行：一个整数，N

第 2..N+1 行：第 i+1 行用空格分隔的两个整数描述奶牛 i 的挤奶间隔。

Output

一行：牛舍必须拥有的最小专用牛棚摊位数量

Sample Input Copy 

5
1 10
2 4
3 6
5 8
4 7

Sample Output Copy 

4

HINT

Time     1  2  3  4  5  6  7  8  9 10
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

加入题单

算法标签：