[长郡中学2004]活动选择

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 active.in 输出文件 active.out

活动选择

【问题描述】

假设有一个需要使用某一资源的n个活动组成的集合S，S={1，2，……，n}。该资源一次只能被一个活动所占用，每一个活动有一个开始时间Bi和结束时间Ei（Bi<=Ei）。若Bi>Ej或者Bj>Ei，则称活动i和活动j兼容。

你的任务是：选择由互相兼容的活动组成的最大集合。

【输入】

输入文件共有n+1行，其中第一行包括一个整数n（2<=n<=1000），n表示活动的总数；接下来的n行对应了这n个活动的开始时间和结束时间（中间用空格隔开）。格式为：

    n

    B1 E1

    B2 E2

    ……

    Bn En

【输出】

输出共1行，为最多的活动数。

【样例】

active.in                          

11                                  
3 5                                
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

active.out 

4

【样例说明】

被选中的活动可以是2.3.6.8号活动，总共有4项。