C++ || Sorting and LIS ||
\nclass Solution {\npublic:\n   \n   int find_bound(vector<int> &dp,int target){\n       \n       int pos = dp.size();\n       \n       int low = 0;\n       int
```\nclass Solution {\npublic:\n   \n   int find_bound(vector<int> &dp,int target){\n       \n       int pos = dp.size();\n       \n       int low = 0;\n       int high = dp.size()-1;\n       \n       while(low<=high){\n           \n           int mid = low + (high-low)/2;\n           \n           if(dp[mid]>=target){\n               pos = mid;\n               high = mid-1;\n           }\n           else{\n               low = mid+1;\n           }\n           \n       }\n       \n       return pos;\n       \n   } \n    \n    \n   int maxEnvelopes(vector<vector<int>>& envelopes) {\n       \n        sort(envelopes.begin(),envelopes.end());\n        \n        for(int i=0;i<envelopes.size();){\n            int start = i;\n            int num = envelopes[i][0];\n           \n            \n            while(i<envelopes.size() && envelopes[i][0]==num){\n                i++;\n            }\n            \n            int end = i-1;\n            \n            reverse(envelopes.begin()+start,envelopes.begin()+end+1);\n            \n        }\n       \n        \n        vector<int> height;\n        \n        for(int i=0;i<envelopes.size();i++){\n            int h = envelopes[i][1];\n            height.push_back(h);\n           \n        }\n       \n        vector<int> dp;\n        \n        for(int i=0;i<height.size();i++){\n            int sz = dp.size();\n            \n            if(sz == 0){\n                dp.push_back(height[i]);\n            }\n            else if(dp[sz-1]<height[i]){\n                dp.push_back(height[i]);\n            }\n            else{\n                // here upper-bound will not work for the test-case--> \n                // [[15,8],[2,20],[2,14],[4,17],[8,19],[8,9],[5,7],[11,19],[8,11],[13,11],[2,13],[11,19],[8,11], [13,11],[2,13],[11,19],[16,1],[18,13],[14,17],[18,19]] \n                \n                // So, here we create custom function for find the exact position for height[i] element in dp array...                \n                int pos = find_bound(dp,height[i]);\n                if(pos >= dp.size()) continue;\n                dp[pos] = height[i];\n                \n            }\n        }\n       \n\t    return dp.size();\n    }\n};\n```
[]