题解 | 信封嵌套

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//贪心+二分查找
int main() {
    int n;
    cin>>n;
    vector<vector<int>> arr(n,vector(2,0));
    for(int i=0;i<n;i++){
        cin>>arr[i][0];
        cin>>arr[i][1];
    }
    //排序，信封，以宽度升序，同宽度，高度降序排列
    if(n==0){
        cout<<0;
        return 0;
    }
    sort(arr.begin(),arr.end(),[](const vector<int>& a,const vector<int>& b){
        return a[0]<b[0] || a[0]==b[0]&& a[1]>b[1];
    });
    //然后新建一个tail,tails[i] 表示长度为 i+1 的递增子序列的最小末尾值
    vector<int> tail;
    for(auto& ele:arr){
        int h=ele[1];
        //返回第一个满足 *it >= value 的迭代器 it
        auto it=lower_bound(tail.begin(), tail.end(), h);
        if(it==tail.end()){
            tail.push_back(h);
        }else{
            *it=h;
        }
    }
    cout<<tail.size();
    return 0;
}
// 64 位输出请用 printf("%lld")