Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- int maxEnvelopes(vector<vector<int>>& envelopes) {
- // Sort the envelopes.
- sort(envelopes.begin(), envelopes.end(), [](auto &a, auto &b){return a[0]<b[0] || (a[0] == b[0] && a[1] > b[1]);});
- // Find lis of height.
- vector<int> seq;
- for(auto &env: envelopes){
- auto it = lower_bound(seq.begin(), seq.end(), env[1]);
- if(it == seq.end())
- seq.push_back(env[1]);
- else
- seq[it-seq.begin()] = env[1];
- }
- return seq.size();
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement