跳至正文
题库4253
#4253

会议中心

查看题目操作

会议中心

题目描述

Siruseri 政府建造了一座会议中心,共有 N 家公司申请租借会堂。第 i 家公司申请的时间为闭区间 [s_i, e_i]:开始日和结束日都占用会堂。会议中心每天最多租给一家公司。

先选出能够接待公司数量最多的方案。如果最优方案有多个,将每个方案中选中的公司编号按升序排列,再选择字典序最小的编号序列。

字典序比较指:在两个序列首次出现不同数字的位置,数字较小的序列更小。公司编号按输入顺序从 1 开始。

例如下表最多接待两家公司,最优方案有 (1,3)、(2,3)、(1,4),最终选择 (1,3)。公司 1 和公司 2 都占用第 9 天,不能同时选中。

公司编号开始日期结束日期
149
2911
31319
41017

输入格式

第一行一个整数 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。

来源

蓝桥杯 算法训练