#P2166. 灯光秀

    ID: 1555 传统题 文件IO:light 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及− 上传者: 标签>贪心基础算法排序数据结构哈希表合肥市蜀山区区赛初中组IO 读写2026

灯光秀

本题需要文件读写

文件 IO 为:输入文件 light.in,输出文件 light.out。请使用上述文件名读入和输出。

问题描述

现有 nn 个灯光秀方案,第 ii 个方案的开始时间为 lil_i,结束时间为 rir_i。

同一时刻只能运行一个方案。若选择两个先后运行的方案,前一个方案的结束时间必须小于等于后一个方案的开始时间。

此外,每个整点时刻最多只能作为两个方案的开始时间。如果原有方案中有 33 个或更多方案的开始时间相同,则以这个时刻为开始时间的所有方案都不能被选中。

请计算最多能选出多少个互不冲突的方案。

输入格式

从文件 light.in 中读入数据。

第一行输入一个整数 nn,表示方案数量。

接下来 nn 行,每行输入两个整数 li,ril_i,r_i,分别表示第 ii 个方案的开始时间和结束时间。

输出格式

输出到文件 light.out 中。

输出一行一个整数,表示最多能选出的方案数量。

样例输入 1

5
1 3
1 5
2 4
4 6
5 7

样例输出 1

2

样例输入 2

5
1 3
1 5
1 7
2 4
5 6

样例输出 2

2

样例输入 3

6
1 2
1 3
1 4
1 5
3 6
4 7

样例输出 3

1

样例输入 4

4
2 5
2 6
3 4
5 8

样例输出 4

2

评测数据规模

对于所有数据,保证 1≤n≤1051\le n\le10^5,0≤li<ri≤1090\le l_i<r_i\le10^9,输入均为整数。

每个测试点 1010 分,各测试点附加限制如下。

测试点 n≤n\le 特殊性质
1∼21\sim2 2020 无
3∼43\sim4 100100 每个开始时间至多对应两个方案
5∼65\sim6 10001000 无
77 所有方案的持续时间相同
88 10510^5 对任意 i<ji<j,有 ri≤ljr_i\le l_j
99 每个开始时间至多对应两个方案
1010 无