C++ | LIS-IMPLEMENTATION | COMPARATOR-TRICK
PLEASE UPVOTE IF U LIKE MY SOLUTION AND EXPLANATION.\n\n\nclass Solution {\npublic:\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        \n        /
**PLEASE UPVOTE IF U LIKE MY SOLUTION AND EXPLANATION.**\n\n```\nclass Solution {\npublic:\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        \n        //sort the given vector in non-decreasing manner onb basis of either height or width\n        //HERE I HAVE SORTED ON THE BASIS OF HEIGHT\n        \n        //we then sort the other parameter in non-increasing manner for similar heights.(i.e., for a pair of\n        //envelop if their heights are same then the one with greater width should come at first than the \n        //lesser one in the sorted array)\n        \n        //we do this because we know that we can only consider one envelop from a group of similar-height\n        //envelops but we cannot claim that we should take the envelop with (minimum of their widths) \n        //as their might be a case [h,w]-->[H,W]  where h<H but w>W or that we take the maximum of their \n        //widths) for case like [H,W]-->[h,w] where H<h and W>w.\n        \n        //so we need an optimal sequence which provide us with longest possible length of envelopes\n        //considering the above cases.\n        \n        \n        //HENCE WE PERFORM LIS ON THE OTHER PARAMETER AFTER SORTING IT IN THE MANNER MENTIONED ABOVE\n        //FOR ENSURING --->[h,w]-->[H,W] for which the W is just greater than w \n        //in the set of [H]->[W1,W2,W3...]\n        \n\t\t//counter case:if we arrange the width in non-decreasing order then we will have a sequence where\n\t\t//width will be in increasing order but we will include similar heights in this case.\n\t\t//eg:[[1,2],[1,3],[2,4],[2,5]]--->if we follow the above method we will get the entire seq (length=4)\n\t\t//as ans but the correct ans is 2.\n\t\t\n     sort(envelopes.begin(),envelopes.end(),[&](const vector<int>& v1,const vector<int>& v2){return v1[0]==v2[0]?v1[1]>v2[1]:v1[0]<v2[0];});\n        \n        vector<int>LIS;\n        for(auto &x:envelopes)\n        {\n            if(LIS.empty()||LIS.back()<x[1])\n                LIS.push_back(x[1]);\n            else\n            {\n                int idx=lower_bound(LIS.begin(),LIS.end(),x[1])-LIS.begin();\n                LIS[idx]=x[1];\n            }\n        }\n        return LIS.size();\n    }\n};\n```
[]