#1068. 活动选择

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Teacher

题目描述

假设有一个需要使用某一资源的n(n≤1000)个活动组成的集合S,S={1,…,n}。该资源一次只能被一个活动占有,每一个活动有一个开始时间bi和结束时间ei(bi≤ei)。若bi>ej或者bj>ei,则活动i和活动j兼容。 你的任务是是:选择由互相兼容的活动组成的最大集合。

输入格式

共n+1行,其中第1行为n,第2行到第n+1行表示n个活动的开始时间和结束时间(中间用一个空格隔开),格式为: n b1 e1 ……. bn en

输出格式

共有两行,第1行为满足要求的活动占用的时间t,第2行为最大集合中的活动序号,每个序号之间用一个空格隔开。

样例

【输入】
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
【输出】
14
2 3 6 8