C++ Solution | Stepwise Explained | Hard problem made easy | Binary Search | Sorting | DP
Intuition and Approach\n\nThe goal is to find the maximum number of envelopes that can be nested inside each other. The sorting is done based on the width, and 
# Intuition and Approach\n\nThe goal is to find the maximum number of envelopes that can be nested inside each other. The sorting is done based on the width, and then the problem is reduced to finding the **Longest Increasing Subsequence (LIS)** based on the height.\n\n1) **Sort Based on Width:**\n-- Sort the envelopes based on the width in ascending order.\n-- If two envelopes have the same width, sort them in descending order of height.\n\n2) **Dynamic Programming (LIS):**\n-- Initialize a vector $$temp$$ to keep track of the heights forming the LIS. \nIterate through the sorted envelopes:\n-- For each envelope, get its height.\n-- If the height is greater than the last element in $$temp$$, add it to the end.\n-- Otherwise, find the first element in $$temp$$ that is greater than or equal to the height, and update it.\n-- The size of the final $$temp$$ vector represents the length of the LIS.\n\n**Key Idea:**\n-- The sorting step helps in simplifying the problem by reducing it to finding the LIS.\n-- The LIS calculation is often done using dynamic programming or binary search.\nThis approach is commonly employed in problems where one needs to find the \n\n\n\n--------------------------------------------------------------------\n\n# Complexity\n- Time complexity: O(N log N + N log K)\n-- where N is the number of envelopes and K is the length of the LIS.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n-------------------------------------------------------------------\n\n#### If you find this solution helpful, consider giving it an upvote!\n\n\n#### Do check out all other solutions posted by me here: https://github.com/adityajamwal02/Leetcode-Community-Solutions\n\n-------------------------------------------------------------------\n\n# Code\n```\nclass Solution {\npublic:\n    static bool compare(vector<int> &a, vector<int> &b){\n        if(a[0]==b[0]){\n            return a[1]>b[1];\n        }\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        vector<int> temp;\n        temp.push_back(envelopes[0][1]);\n        for(int i=1;i<n;i++){\n            int height=envelopes[i][1];\n            if(height>temp.back()){\n                temp.push_back(height);\n            }else{\n                auto it = lower_bound(temp.begin(),temp.end(),height);\n                *it=height;\n            }\n        }\n    return temp.size();      \n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Sorting', 'C++']