活动选择 (act)

活动选择 (act)

测试数据来自 wjszez/1010

【问题描述】假设有一个需要使用某一资源的n个活动组成的集合S,S={1,……,n}。该资源一次只能被一个活动所占用,每一个活动有一个开始时间bi和结束时间ei (bi≤ei)。若bi≥ej或者bj≥ei,则活动i和活动j兼容。
你的任务是:选择由互相兼容的活动组成的最大集合。
【输入数据】
输入文件名为:act.in,共n+1行,其中第1行为n,第2行到第n+1行表示n个活动的开始时间和结束时间(中间用空格隔开),格式为:
n
b1 e1
… …
bn en
【输出数据】
输出文件名为:act.out,共两行,第1行为满足要求的活动占用的时间t,第2行为最大集合中的活动序号,每个数据之间用一个空格隔开【测试样例】
【测试样例】
act.in
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
57
3 8
5 9
2 13
act.out
14
2 3 6 8

信息

ID
1012
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者