[C++] Explaination why sort like that works?  || LIS + Binary search
The question can be confusing even though you know the solution of classic lis using binary search.I recommend learning first the Binary search solution of clas
The question can be confusing even though you know the solution of classic lis using binary search.I recommend learning first the Binary search solution of classic LIS. \nThe sorting part caused a lot of confusion to me also ;)\n\n**This post focuses on why sorting a particular way yields the solution**\n\nFor a envelope A to go inside B, lengthA < lengthB and widthA < widthB\n1. We cannot take care of both parameters simontaneously, so lets sort according to one paremeter lets say height , and take care of other parameter while forming the solution.\n2. Lets say we have dolls \n\t[2,6] , [2,3], [4,5] , [5,7] ,[8,9], [4,7], [6,9]\napply sort acc to 0\'th index , (we will see how later we need to modify the sort a little bit)\n\t[2,6], [2,3], [4,5], [4,7] , [5,7], [6,9], [8,9]\n\n**general idea behind binary search solution is that if we cant add the current candidate to the end , we should start forming a new solution simultaneously . So lets try this approach on the example and see how it fails**\n[2,6]     \n\n[2,6]                                               since [2,3] cant be fitted because of short 1\'st index(call height)\n[2,3]\n\n[2,6]                                                height [4,5] is shorter\n[2,3], [4,5]\n\n[2,6],[4,7]\n[2,3],[4,5], [4,7]                              height[4,7] big enough to fit in both\n\nWait but we just hit an invalid sequence [2,3],[4,5],[4,7]. This happened because of equal widths of [4,5],[4,7] but why it didnt happen when we considered the dolls [2,6],[2,3]?\n\n**Reason**: If among envelopes having same width , if we consider any envelope having height smaller first then the higher height envelopes will start contributing the solution of smaller ones which is actually invalid.\nBut as we saw in case of [2,3] and [2,6] , [2,3] instead of contributing, started its own new solution.\n**The new new sorting we have now is**\n**sort in increasing according to width and incase of equal widths sort according to the lengths.**\n\nThe rest solution is same as the classic LIS.\n**Hope it helps:) Do upvote**\n```\nclass Solution {\npublic:\n    static bool compare(vector<int> &a , vector<int> &b){\n        if(a[0]==b[0]) return a[1]>b[1];\n        return a[0]<b[0];\n    }\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        int n=envelopes.size();\n        sort(envelopes.begin(),envelopes.end(),compare);\n        \n        vector<int> lis;\n        for(int i=0;i<n;i++){\n            int ht = envelopes[i][1];\n            auto idx = lower_bound(lis.begin(),lis.end(),ht)-lis.begin();\n            if(idx==lis.size())\n                lis.push_back(ht);\n            else lis[idx]=ht;\n        }\n        \n        return lis.size();\n    }\n};\n```
[]