using dynamic programming (binary search on LIS)
Intuition\nTo find the maximum number of envelopes that can be nested (Russian-dolled), we need to treat it like finding the Longest Increasing Subsequence (LIS
# Intuition\nTo find the maximum number of envelopes that can be nested (Russian-dolled), we need to treat it like finding the Longest Increasing Subsequence (LIS), but in two dimensions (width and height). By sorting and then applying a modified LIS algorithm, we can efficiently solve the problem.\n\n# Approach\nSorting:\nSort the envelopes by width in ascending order. If two envelopes have the same width, sort them by height in descending order. This ensures that when we consider heights, we only need to find increasing sequences.\n\nLIS with Binary Search:\nAfter sorting, extract the heights of the envelopes and find the length of the LIS using a dynamic programming approach combined with binary search.\nUse a vector dp to store the current LIS. For each height, use lower_bound to find its position in dp. If it\'s greater than all elements, append it. Otherwise, replace the existing element.\n\n\n# Complexity\n- Time complexity:\nSorting the envelopes take  O(nlogn).\nFinding the LIS with binary search for each height takes O(nlogn).\nThus, the overall time complexity is O(nlogn).\n\n- Space complexity:\nThe dp vector used to store the heights takes O(n) space in the worst case.\nHence, the space complexity is O(n).\n\n# Code\n```\nclass Solution {\npublic:\nstatic bool comp(vector<int>&p1,vector<int>&p2){\n    if(p1[0]==p2[0])\n    return p1[1]>p2[1];\n    return p1[0]<p2[0];\n}\n    int maxEnvelopes(vector<vector<int>>& en) {\n        int n=en.size();\n        sort(en.begin(),en.end(),comp);\n        vector<int>dp;\n        int maxi=1;\n        for(int i=0;i<n;i++){\n            int height=en[i][1];\n            auto it=lower_bound(dp.begin(),dp.end(),height);\n            if(it==dp.end())\n            dp.push_back(height);\n            else\n            *it=height;\n        }\n        return dp.size();\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'C++']