Let \(\lbrace i\rbrace\) denote apple \(i\).

Define the ordering between two apples\(\lbrace i\rbrace,\lbrace j\rbrace\) as \(\lbrace i\rbrace \le \lbrace j\rbrace \Leftrightarrow |X_i-X_j|\le T_j - T_i\). Then a set of apples \(S\) can be collected by one robot if and only if any two elements in \(S\) are comparable.

By substituting variables as \((u_i,v_i)=(T_i+X_i,T_i-X_i)\), we see \(|X_i-X_j|\le T_j - T_i\) if and only if \(u_i \le u_j\) and \(v_i\le v_j\). From now on, we will consider \(X_i\) and \(T_i\) instead of \(u_i\) and \(v_i\).

The ordering of apples is transitive, reflexive, and anti-symmetric, so the set of apples is a finite partially ordered set (poset). Since the sought value is the minimum number of chains that cover the set, Dilworth’s theorem tells that the sought value equals the size of a largest anti-chain in this finite poset.

(Chain: a set where any two elements are comparable)

(Chain: a set where any two elements are incomparable)

When \((u_i,v_i)\) are sorted lexicographically, for \(i < j\),\(\lbrace i\rbrace\) and \(\lbrace j\rbrace\) are incomparable if and only if \(v_i > v_j\). Therefore, this problem boils down to finding the length of a longest strictly monotonically decreasing subsequence, which can be solved in \(O(N\log N)\) time.

The problem can be solved by appropriately implementing this algorithm. The time complexity is \(O(N\log N)\).

Sample code (Python 3)

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))