1151. [长郡中学2004] 活动选择

【问题描述】

假设有一个需要使用某一资源的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个活动的开始时间和结束时间（中间用空格隔开）。

【输出格式】

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

【输入样例】

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

【输出样例】

4

【样例说明】

被选中的活动可以是2、3、6、8号活动，总共有4项。