blob: fce0aa394fc0613d5bc5daaf315aebaeefc9558d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include "leetcode.h"
class Solution {
public:
int maxEnvelopes(vector<vector<int>> &envelopes) {
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(), compare);
vector<int> ans;
for (int i = 0; i < envelopes.size(); i++) {
int candidate = envelopes[i][1];
int idx = lower_bound(ans.begin(), ans.end(), candidate) - ans.begin();
if (idx >= ans.size())
ans.push_back(candidate);
else
ans[idx] = candidate;
}
return ans.size();
}
private:
static bool compare(vector<int> &a, vector<int> &b) {
if (a[0] == b[0])
return a[1] > b[1];
return a[0] < b[0];
}
};
int main() {}
|