OpenJudge

22:某校活动安排

总时间限制:
1000ms
内存限制:
65536kB
描述

某校n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一个教室,而在同一时间内只有一个活动能使用这个教室。每个活动i都有一个要求使用该教室的起始时间si和一个结束时间fi,si 。如果选择了活动i,则它在封闭时间区间[si, fi]内占用该教室。若区间[si, fi]与区间[sj, fj]不相交,则称活动i与活动j是相容的。也就是说,当si>fjsj>fi时,活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。


输入
输入文件包含n+1行: 
第1行包括一个整数n,为活动的个数N不大于50。 
第2~n+1行每行包含一个两个正整数,分别表示对应的活动的开始时间和结束时间。
输出
输出文件仅一行,包含一个整数,即最多可以安排的活动个数。
样例输入
11
1 4
2 13
3 5
5 7
5 9
8 11
6 10
0 6
8 12
3 8
12 14
样例输出
4
全局题号
16968
添加于
2018-04-02
提交次数
87
尝试人数
57
通过人数
55