Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:512 MB

#1000. 「一本通 1.1 例 1」活动安排

统计

题目描述

设有个 $ n $ 活动的集合 $ E= \{1 , 2 , \cdots , n \} $ ,其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动 $ i $ 都有一个要求使用该资源的起始时间 $ s _ {i} $ 和一个结束时间 $ f _ {i} $ ,且 $ s _ {i} < f _ {i} $ 。如果选择了活动 $ i $ ,则它在时间区间 $[ s _ {i} , f _ {i}) $ 内占用资源。若区间 $[ s _ {i} , f _ {i}) $ 与区间 $[ s _ {j} , f _ {j}) $ 不相交,则称活动 $ i $ 与活动 $ j $ 是相容的。也就是说,当 $ f _ {i} \leq s _ {j} $ 或 $ f _ {j} \leq s _ {i}$ 时,活动 $ i $ 与活动 $ j $ 相容。选择出由互相兼容的活动组成的最大集合。

输入格式

第一行一个整数 $ n $ ;

接下来的 $ n $ 行,每行两个整数 $ s _ {i} $ 和 $ f _ {i} $ 。

输出格式

输出互相兼容的最大活动个数。

样例

样例输入

4
1 3
4 6
2 5
1 7

样例输出

2

数据范围与提示

$1 \leq n \leq 1000$