リンゴ \(i\) を \(\lbrace i\rbrace\) と表記します。

\(2\) つのリンゴ \(\lbrace i\rbrace,\lbrace j\rbrace\) の大小関係を \(\lbrace i\rbrace \le \lbrace j\rbrace \Leftrightarrow |X_i-X_j|\le T_j - T_i\) で定義します。この時、リンゴの集合 \(S\) に対し \(S\) が \(1\) 台のリンゴロボで回収できることは \(S\) 内の任意の \(2\) つの要素が比較可能であることと同値です。

ここで、\((u_i,v_i)=(T_i+X_i,T_i-X_i)\) という変数変換を行うと \(|X_i-X_j|\le T_j - T_i\) は \(u_i \le u_j\) かつ \(v_i\le v_j\) という条件と同値になります。以降は \(X_i,T_i\) の代わりに \(u_i,v_i\) を考えます。

リンゴ同士に定義した大小関係は推移律・反射律・反対称律を満たすので、この大小関係におけるリンゴの集合は有限半順序集合となります。さらに、求める値はリンゴの集合を分割するために必要な最小の鎖の個数であることを踏まえると、Dilworth の定理より求める値はこの有限半順序集合における最大反鎖の大きさと一致します。

（鎖：どの \(2\) つの要素も比較可能な集合のこと）

（反鎖：どの \(2\) つの要素も比較不能な集合のこと）

\((u_i,v_i)\) を辞書順にソートすると、\(i < j\) に対し \(\lbrace i\rbrace\) と \(\lbrace j\rbrace\) が比較不能であることは \(v_i > v_j\) であることと一致します。したがって、この問題は \((v_1,v_2,\ldots,v_N)\) の狭義単調減少部分列の長さの最大値を求める問題に帰着され、これは \(O(N\log N)\) 時間で解くことができます。

以上を適切に実装することでこの問題を解くことができます。計算量は \(O(N\log N)\) です。

実装例(Python3)

import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
a = []
for i in range(n):
    t, x = map(int, input().split())
    a.append((t + x, t - x))
a.sort()
lis = []
for i in range(n):
    v = -a[i][1]
    if len(lis) == 0 or v > lis[-1]:
        lis.append(v)
    else:
        lis[bisect_left(lis, v)] = v
print(len(lis))