#P2166. 灯光秀
灯光秀
本题需要文件读写
文件 IO 为:输入文件
light.in,输出文件light.out。请使用上述文件名读入和输出。
问题描述
现有 个灯光秀方案,第 个方案的开始时间为 ,结束时间为 。
同一时刻只能运行一个方案。若选择两个先后运行的方案,前一个方案的结束时间必须小于等于后一个方案的开始时间。
此外,每个整点时刻最多只能作为两个方案的开始时间。如果原有方案中有 个或更多方案的开始时间相同,则以这个时刻为开始时间的所有方案都不能被选中。
请计算最多能选出多少个互不冲突的方案。
输入格式
从文件 light.in 中读入数据。
第一行输入一个整数 ,表示方案数量。
接下来 行,每行输入两个整数 ,分别表示第 个方案的开始时间和结束时间。
输出格式
输出到文件 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
评测数据规模
对于所有数据,保证 ,,输入均为整数。
每个测试点 分,各测试点附加限制如下。
| 测试点 | 特殊性质 | |
|---|---|---|
| 无 | ||
| 每个开始时间至多对应两个方案 | ||
| 无 | ||
| 所有方案的持续时间相同 | ||
| 对任意 ,有 | ||
| 每个开始时间至多对应两个方案 | ||
| 无 |