2701: 「一本通 1.1 例 1」活动安排
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:101
Solved:57
Description
有 $n$ 个活动,编号为 $1, 2, \dots , n$ ,其中每个活动 $i$ 都有一个要求使用该资源的起始时间 $s$ 和一个结束时间 $f$ ,且如果选择了活动 $i$ ,则它在时间区间 $\lbrack s_i, f_i)$ 内进行。若区间 $\lbrack s_i, f_i)$ 与区间 $\lbrack s_j, f_j)$ 不相交,则称活动 $i$ 和活动 $j$ 是兼容的。也就是说,当且仅当 $f_i \leq s_j$ 或 $f_j \leq s_i$ 时,活动 $i$ 与活动 $j$ 兼容。求出最多可以选出几个互相兼容的活动。
Input
第一行一个整数 $n$ ;
接下来的 $n$ 行,每行两个整数 $s_i$ 和 $f_i$ 。
Output
输出互相兼容的活动的最大个数。
Sample Input Copy
4
1 3
4 6
2 5
1 7
Sample Output Copy
2
HINT
$1 \leq n \leq 1000$