Expert.
Put your skills to the test.

Problem summary

Delivery request i must be served at house Hi exactly at time Ti. Trucks move at speed at most one house per time unit, may wait, and may start anywhere. Find the minimum number of trucks needed to serve every request.

Constraints

1≤N≤1000000; 1≤Ti,Hi≤1000000000; no two requests have the same time and house.

Worked example

Original statement sample.

6
1 1
2 3
3 2
5 4
4 1
4 3

2

Solution analysis

1. A truck can serve request i before j exactly when Tj−Ti≥|Hj−Hi|. Rearranging the two inequalities gives Ti−Hi≤Tj−Hj and Ti+Hi≤Tj+Hj. Transform each request into (u,v)=(T−H,T+H).
2. Sort by u and then by v. The route of one truck is now a nondecreasing subsequence of v. Equal u values must be sorted by increasing v, because such requests can belong to the same route.
3. Keep one multiset entry for the last v on each current route. For a new v, extend the route with the largest last value no greater than v. If no such route exists, buy a new truck. Keeping the smaller eligible tails unchanged preserves the most flexibility for future requests.
4. The sample can be split between two trucks, as described by the source. For a smaller illustration, transformed values v=3,1,2 need two routes: put3 on one route and1,2 on the other. A single route cannot decrease from3 to1.

Why it works

The transformation is equivalent to physical reachability, so routes are exactly chains in the two-dimensional dominance order. In sorted-u order, extending the largest eligible tail is safe by exchange: using a smaller eligible tail instead leaves the larger one less useful, and swapping their future assignments preserves feasibility. When no tail is eligible, a new route is unavoidable in an optimal greedy chain cover. Thus the final number of routes is minimum.

Watch out. Sort equal first coordinates increasingly by the second. Use upper_bound(v), then step back, so equal tails are eligible. Starting positions are unrestricted; do not impose a depot constraint absent from the statement.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<pair<long long,long long>>requests;
    for(int i=0;i<n;i++){
        long long time;
        long long house;
        cin>>time>>house;
        requests.push_back({time-house,time+house});
    }
    sort(requests.begin(),requests.end());
    multiset<long long>tails;
    for(auto[first,second]:requests){
        (void)first;
        auto next=tails.upper_bound(second);
        if(next!=tails.begin()){
            // Reuse the least flexible route that can reach this request.
            --next;
            tails.erase(next);
        }
        tails.insert(second);
    }
    cout<<tails.size()<<'\n';
}