分数: 450 点
问题陈述
有 N 产品贴有标签 1 to N 在传送带上流动。 Keyence 打印机连接到传送带上,并且产品 i 进入打印机的范围 T_i 从现在开始微秒并离开它 D_i 微秒后。
Keyence 打印机可以立即在打印机范围内的一件产品上进行打印(特别是,可以在产品进入或离开打印机范围时进行打印)。 然而,打印一次后,需要充电时间 1 微秒后才能再次打印。 当选择最佳的产品和打印机打印时间时,打印机最多可以打印多少个产品?
约束
- 1\leq N \leq 2\times 10^5
- 1\leq T_i,D_i \leq 10^{18}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N T_1 D_1 T_2 D_2 \vdots T_N D_N
输出
打印打印机可以打印的最大产品数量。
样本输入 1
5 1 1 1 1 2 1 1 2 1 4
示例输出 1
4
下面,我们将简单地调用该时刻 t 从现在开始的微秒时间 t.
例如,您可以在四种产品上打印,如下所示:
- 时间 1 :产品 1,2,4,5 输入打印机的范围。在产品上打印 4.
- 时间 2 :产品 3 进入打印机范围,产品 1,2 离开打印机的范围。在产品上打印 1.
- 时间 3 :产品 3,4 离开打印机的范围。在产品上打印 3.
- 时间 4.5 : 在产品上打印 5.
- 时间 5 :产品 5 离开打印机的范围。
不可能在所有五种产品上打印,所以答案是 4.
示例输入 2
2 1 1 1000000000000000000 1000000000000000000
示例输出 2
2
示例输入 3
10 4 1 1 2 1 4 3 2 5 1 5 1 4 1 2 1 4 1 2 4
示例输出 3
6