4275: 自私的放牧Selfish Grazing
[Creator : ]
Description
Each of Farmer John's $N\ (1 \leq N \leq 50,000)$ cows likes to graze
in a certain part of the pasture, which can be thought of as a large
one-dimeensional number line. Cow i's favorite grazing range starts at
location $S_i$ and ends at location $E_i\ (1 \leq S_i < E_i,\ S_i <
E_i \leq 100,000,000)$.
Most folks know the cows are quite selfish; no cow wants to share any of its grazing area with another. Thus, two cows $i$ and $j$ can only graze at the same time if either $S_i >= E_j$ or $E_i <= S_j$. FJ would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences.
Consider a set of $5$ cows with ranges shown below:
For a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.
约翰有 $N\ (1≤N≤50000)$ 头牛，约翰的草地可以认为是一条直线．每只牛只喜欢在某个特定的范围内吃草．第i头牛喜欢在区间 $(S_i,\ E_i)$ 吃草，$1≤S_i<E_i≤1,000,000,00$
奶牛们都很自私，他们不喜欢和其他奶牛共享自己喜欢吃草的领域，因此约翰要保证任意
两头牛都不会共享他们喜欢吃草昀领域．如果奶牛 $i$ 和奶牛 $j$ 想要同时吃草，那么要满足：$S_i\geq E_j$ 或者 $E_i≤S_j$．约翰想知道在同一时刻，最多可以有多少头奶牛同时吃草？
Most folks know the cows are quite selfish; no cow wants to share any of its grazing area with another. Thus, two cows $i$ and $j$ can only graze at the same time if either $S_i >= E_j$ or $E_i <= S_j$. FJ would like to know the maximum number of cows that can graze at the same time for a given set of cows and their preferences.
Consider a set of $5$ cows with ranges shown below:
... 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
... |----|----|----|----|----|----|----|----|----|----|----|----|----
Cow 1: <===:===> : : :
Cow 2: <========:==============:==============:=============>:
Cow 3: : <====> : : :
Cow 4: : : <========:===> :
Cow 5: : : <==> : :
These ranges represent $(2,\ 4),\ (1,\ 12),\ (4,\ 5),\ (7,\ 10)$, and $(7,\ 8)$, respectively. For a solution, the first, third, and fourth (or fifth) cows can all graze at the same time. If the second cow grazed, no other cows could graze. Also, the fourth and fifth cows cannot graze together, so it is impossible for four or more cows to graze.
约翰有 $N\ (1≤N≤50000)$ 头牛，约翰的草地可以认为是一条直线．每只牛只喜欢在某个特定的范围内吃草．第i头牛喜欢在区间 $(S_i,\ E_i)$ 吃草，$1≤S_i<E_i≤1,000,000,00$
奶牛们都很自私，他们不喜欢和其他奶牛共享自己喜欢吃草的领域，因此约翰要保证任意
两头牛都不会共享他们喜欢吃草昀领域．如果奶牛 $i$ 和奶牛 $j$ 想要同时吃草，那么要满足：$S_i\geq E_j$ 或者 $E_i≤S_j$．约翰想知道在同一时刻，最多可以有多少头奶牛同时吃草？
Input
* Line 1: A single integer: $N$
* Lines $2$..$N+1$: Line $i+1$ contains the two space-separated integers: $S_i$ and $E_i$
* Lines $2$..$N+1$: Line $i+1$ contains the two space-separated integers: $S_i$ and $E_i$
Output
* Line 1: A single integer representing the maximum number of cows that can graze at once.
Sample 1 Input
5
2 4
1 12
4 5
7 10
7 8
Sample 1 Output
3