C++ easy dp solution in O(nlogn) time and O(n) space with explanation
This question is a varation of Longest increasing subsequence problem. We need to find the largest number of rectangles which can be russian doll. So, we need t
This question is a varation of Longest increasing subsequence problem. We need to find the largest number of rectangles which can be russian doll. So, we need to first sort the numbers with respect to height or width. I have sorted the number according to width. Also, it is given that the height and width should be strictly greater so, to for that while sorting we need to take care that when the width are equal, then we must sort them according to decreaing height. This is done so that we don\'t include the equal heights sequence in the answer.\n\n```\nclass Solution {\npublic:\n   static bool func(vector<int>& e1, vector<int>& e2){\n         return (e1[0]==e2[0])?e1[1]>e2[1]:e1[0]<e2[0];\n    }\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n        sort(envelopes.begin(),envelopes.end(),func);\n        vector<int> v;\n        for(int i=0;i<envelopes.size();i++)\n        {\n            if(i==0 || envelopes[i][1]>v[v.size()-1])\n               {\n                   v.push_back(envelopes[i][1]);\n               }\n               else\n               {\n                   int index=binarysearch(v,envelopes[i][1]);\n                   v[index]=envelopes[i][1];\n               }\n        }\n     return v.size();           \n    }\n    \n    int binarysearch(vector<int> &v,int x)\n    {\n        int i=0;\n        int j=v.size()-1;\n        int ans=0;\n        while(i<=j)\n        {\n            int mid=(i+(j-i)/2);\n            if(v[mid]==x)\n                return mid;\n            else if(v[mid]>x)\n            {\n                ans=mid;\n                j=mid-1;\n            }\n            else\n                i=mid+1;\n        }\n        return ans;\n    }\n   \n};\n```
['Binary Search', 'Dynamic Programming', 'C', 'C++']