First, consider the following algorithm.

• For each \(t=1,2,3,\dots,\) in order,
  • if there is an unprinted product within the range of the printer at \(t\), then print on the one with the earliest exit time among them.

This greedy algorithm is correct. We omit the formal proof, but it can be shown by the fact that printing at a non-integer time is not beneficial, and that if there is an optimal solution that violates the strategy above at time \(t\), we can safely replace that action with one obeying the greedy strategy (keeping it optimal).

However, \(t\) can be at most \(10^{18}\), so a naive implementation will not past. Instead, consider the following optimization.

• If at some time \(t\), there is no printable product (i.e. there is no unprinted product within the range of the printer), then let \(t \leftarrow t'\), where \(t'\) is the first time on which a product enters the range of the printer later than \(t\).

This is obviously valid because no product can be printed on between time \(t\) and time \(t'\). By this optimization, we only have to inspect \(O(N)\) timestamps \(t\). One can choose the product with the earliest exit time using a priority queue in \(O(\log N)\) time, and one can find \(t'\) (when no products are printable) using a binary search or a sliding window technique in \(O(\log N)\) or \(O(1)\) time, so the overall complexity is \(O(N \log N)\) time.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<pair<ll, ll>> v;
    for (int i = 0; i < n; i++) {
        ll t, d;
        cin >> t >> d;
        v.emplace_back(t, t + d);
    }
    sort(v.begin(), v.end());
    priority_queue<ll, vector<ll>, greater<>> pq;
    int it = 0;
    int ans = 0;
    for (ll i = 0;; i++) {
        if (pq.empty()) {
            if (it == n) break;
            i = v[it].first;
        }
        while (it < n and v[it].first == i) {
            pq.push(v[it++].second);
        }
        while (!pq.empty() and pq.top() < i) pq.pop();
        if (!pq.empty()) {
            pq.pop();
            ++ans;
        }
    }
    cout << ans << endl;
}