AT_abc325_d [ABC325D] Printing Machine

题目描述

有 $N$ 个编号从 $1$ 到 $N$ 的商品在传送带上流动。传送带上安装有印字机，第 $i$ 个商品将在现在起 $T_i$ $\mu s$ 后进入印字机的范围，并在进入后 $D_i$ $\mu s$ 后离开印字机的范围。

Keyence 的印字机可以在一瞬间对处于印字机范围内的任意一个商品进行印字（特别地，也可以在商品刚进入或即将离开印字机范围的瞬间进行印字）。但是，每次印字后，必须等待 $1$ $\mu s$ 的充能时间，才能进行下一次印字。请问，如果合理选择印字的商品和时机，最多可以对多少个商品进行印字？

输入格式

输入以以下格式从标准输入读入。

$N$
$T_1$ $D_1$
$T_2$ $D_2$
$\vdots$
$T_N$ $D_N$

输出格式

输出印字机最多能够印字的商品数量。

输入输出样例 #1

输入 #1

5
1 1
1 1
2 1
1 2
1 4

输出 #1

4

输入输出样例 #2

输入 #2

2
1 1
1000000000000000000 1000000000000000000

输出 #2

2

输入输出样例 #3

输入 #3

10
4 1
1 2
1 4
3 2
5 1
5 1
4 1
2 1
4 1
2 4

输出 #3

6

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq T_i, D_i \leq 10^{18}$
• 输入均为整数

样例解释 1

以下将“现在起 $t$ $\mu s$ 后”简称为时刻 $t$。例如，可以如下方式对 $4$ 个商品进行印字：

• 时刻 $1$：商品 $1,2,4,5$ 进入印字机范围。对商品 $4$ 进行印字。
• 时刻 $2$：商品 $3$ 进入印字机范围，商品 $1,2$ 离开印字机范围。对商品 $1$ 进行印字。
• 时刻 $3$：商品 $3,4$ 离开印字机范围。对商品 $3$ 进行印字。
• 时刻 $4.5$：对商品 $5$ 进行印字。
• 时刻 $5$：商品 $5$ 离开印字机范围。

无法对全部 $5$ 个商品进行印字，因此答案为 $4$。

由 ChatGPT 4.1 翻译