题解 | 信封嵌套

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;

    sort(a.begin(), a.end(), [](const auto & x, const auto & y) {
        if (x.first != y.first) return x.first < y.first; // 长升序
        return x.second > y.second;                       // 同长宽降序
    });

    vector<int>
    tails;               // tails[k]：长度为 k+1 的序列最小可能尾宽
    for (auto& e : a) {
        int w = e.second;
        auto it = lower_bound(tails.begin(), tails.end(), w); // 严格递增
        if (it == tails.end()) tails.push_back(w);
        else *it = w;
    }
    cout << (int)tails.size() << '\n';
    return 0;
}