Untitled

 avatar
unknown
plain_text
a year ago
528 B
4
Indexable
class Solution {
public:
    static bool cmp(const vector<int>&a,const vector<int>&b) {return (a[0]==b[0])?a[1]>b[1]:a[0]<b[0];}
    int maxEnvelopes(vector<vector<int>>& env) {
        int n=env.size();
        vector<int>lis;
        sort(env.begin(),env.end(),cmp);

        for(int i=0;i<n;i++){
            int el=env[i][1];
            int ind =lower_bound(lis.begin(),lis.end(),el)-lis.begin();
            if(ind==lis.size()) lis.push_back(el);
            else lis[ind]=el;
        }
        return lis.size();
    }
};
Editor is loading...
Leave a Comment