#4253
会议中心
会议中心
题目描述
Siruseri 政府建造了一座会议中心,共有 N 家公司申请租借会堂。第 i 家公司申请的时间为闭区间 [s_i, e_i]:开始日和结束日都占用会堂。会议中心每天最多租给一家公司。
先选出能够接待公司数量最多的方案。如果最优方案有多个,将每个方案中选中的公司编号按升序排列,再选择字典序最小的编号序列。
字典序比较指:在两个序列首次出现不同数字的位置,数字较小的序列更小。公司编号按输入顺序从 1 开始。
例如下表最多接待两家公司,最优方案有 (1,3)、(2,3)、(1,4),最终选择 (1,3)。公司 1 和公司 2 都占用第 9 天,不能同时选中。
| 公司编号 | 开始日期 | 结束日期 |
|---|---|---|
| 1 | 4 | 9 |
| 2 | 9 | 11 |
| 3 | 13 | 19 |
| 4 | 10 | 17 |
输入格式
第一行一个整数 N。接下来 N 行,每行两个整数 s_i、e_i,表示第 i 家公司的开始、结束日期。
输出格式
第一行输出最多可以接待的公司数 M。第二行按升序输出选中的 M 个公司编号,用空格分隔,构成最优方案中的最小字典序。
样例
4
4 9
9 11
13 19
10 17
2
1 3
数据范围
1 ≤ N ≤ 200000,1 ≤ s_i ≤ e_i ≤ 109。
50% 的数据满足 N ≤ 3000。