Problem 1324. -- [Usaco2009 Dec]Selfish Grazing 自私的食草者

1324: [Usaco2009 Dec]Selfish Grazing 自私的食草者

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 73  Solved: 47
[Submit][Status][Web Board]

Description

约翰有N(1≤N≤50000)头牛,约翰的草地可以认为是一条直线.每只牛只喜欢在某个特定的范围内吃草.第i头牛喜欢在区间(Si,Ei)吃草,1≤Si 奶牛们都很自私,他们不喜欢和其他奶牛共享自己喜欢吃草的领域,因此约翰要保证任意
两头牛都不会共享他们喜欢吃草昀领域.如果奶牛i和奶牛J想要同时吃草,那么要满足:Si>=Ej或者Ei≤Sj.约翰想知道在同一时刻,最多可以有多少头奶牛同时吃草?

Input

第1行:一个整数N.
第2到N+1行:第i+l行有两个整数Si,Ei.

Output

一个整数,最多可以有多少头牛同时吃草.

Sample Input

5
2 4
1 12
4 5
7 10
7 8

Sample Output

3
第1,3,4共3只奶牛可以同时吃草,第1,3,5也可以.

HINT

Source

[Submit][Status]