abc 325 D

贪心，和区间覆盖问题有点关联，先对起点排序，然后对于每个位置考虑。
用单调队列，将起点小于等于的存入
然后考虑该位置要消除那个区间，优先考虑终点靠前的，如果堆中没有区间终点，需要从下个区间的起点开始考虑

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> PII;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<PII> seg(n);

    for (int i = 0; i < n; i ++) {
        ll s, d;
        cin >> s >> d;
        seg[i] = {s, s + d};
    }

    sort(seg.begin(), seg.end());

    priority_queue<ll, vector<ll>, greater<>> q;
    int it = 0;
    int ans = 0;

    for (ll i = 0; ; i ++) {
        if (q.empty() && it == n) break;
        if (q.empty() && i < seg[it].first) i = seg[it].first;
        while (it < n && i == seg[it].first) q.push(seg[it ++].second);

        while (!q.empty() && q.top() < i) q.pop();

        if (!q.empty() && q.top() >= i) {
            ans ++;
            q.pop();
        }
    }

    cout << ans << endl;

    return 0;
}