A137129.展厅排期
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
学校科技节有很多展演活动,每个活动都需要占用同一个展厅。
第 i 个活动从时刻 si 开始,持续 di 个单位时间,也就是说它会占用闭区间:[si,si+di−1]。
为了重新布置展厅,如果一个活动在时刻 r 结束,那么下一个被安排的活动的开始时刻至少需要满足:l≥r+c+1
其中 c 表示两个活动之间必须空出的整理时间。
Sherry 想从所有活动中选出尽量多的活动安排进展厅,请你求出最多可以安排多少个活动。
输入格式
第一行输入两个整数 n,c,分别表示活动数量和整理时间。
接下来 n 行,每行输入两个整数 si,di,表示第 i 个活动的开始时刻和持续时间。
输出格式
输出一个整数,表示最多可以安排的活动数量。
输入输出样例
输入#1
6 1 1 2 3 2 5 1 6 2 8 1 2 1
输出#1
3
说明/提示
数据范围
1≤n≤2×105
0≤c≤109
1≤si,di≤109
输入解题思路,AI测评打分。不知道怎么写?