問題概要

$N$ 個の商品がベルトコンベアで運ばれてくる。 $i$ 番目の商品は、時刻 $T_{i}$ から時刻 $T_{i} + D_{i}$ の間 (両端含む) に点字できる。

点字マシンは 1 秒あたり 1 個の商品にしか点字できない (正確には、1 個に点字したら、1 秒起動できない)。

最大で何個の商品に点字できるかを求めよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

一旦、区間の左端でソートして考えることにした。

最初の重要な考察として、もし、開始時刻が最も早い区間が単独で存在していたら、その区間は開始時刻で点字してしまってよいと言える。それによって他の区間には一切の不都合がないからだ。

問題なのは、最も早い開始時刻にタイがあるとき......この場合は、今度は終了時刻が早いものから優先的に選べばよい。その方が、後が楽になるからだ。ちゃんと示すなら、いつもの「交換しても悪化しない」という議論ができる。

注意したいのは、

区間 [1, 2, 3, 4]
区間 [1, 2, 3, 4, 5]
区間 [1, 2, 3, 4, 5, 6]
区間 [2, 3]

というようなケースだ。さっきのルールに従うと、最初に区間 [1, 2, 3, 4] を時刻 1 に点字することになる。この次、点字可能時刻が 2 以降になる。この場合は、区間 [2, 3] も含めることにするとよい。つまり、

区間 [1, 2, 3, 4, 5]
区間 [1, 2, 3, 4, 5, 6]
区間 [2, 3]

の中で最も終了時刻が早い区間を選ぶことになる。

一般化

以上を一般化すると、こんな感じに。

区間の集合 $S$ を管理する。初期状態では $S$ は空である。

時刻を順に進めていく。前回点字した時刻を $t$ とする (初期状態では $t = 0$ などとしておく)。そして、時刻 $t+1$ 以降で最も早い区間の開始時刻を $t'$ とする。

このとき、区間の集合 $S$ に対して、開始時刻が $t'$ であるような区間を追加する。そして、区間の集合 $S$ の中で、最も終了時刻が早いものを選べば良い。

以降、これを繰り返す。

計算量は $O(N \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
using pll = pair<long long, long long>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<pll> ts(N);
    for (int i = 0; i < N; ++i) {
        cin >> ts[i].first >> ts[i].second;
        ts[i].second += ts[i].first;
    }
    sort(ts.begin(), ts.end());
    
    priority_queue<long long, vector<long long>, greater<long long>> que;
    int res = 0, iter = 0;
    long long nex_time = 0;
    while (iter < N || !que.empty()) {
        if (iter < N && que.empty()) nex_time = ts[iter].first;
        while (iter < N && ts[iter].first == nex_time) {
            que.push(ts[iter++].second);
        }
        while (!que.empty() && que.top() < nex_time) que.pop();
        if (!que.empty()) {
            que.pop();
            ++res;
            ++nex_time;
        }
    }
    cout << res << endl;
}