-
Notifications
You must be signed in to change notification settings - Fork 3
/
354.cpp
32 lines (31 loc) · 1.05 KB
/
354.cpp
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
29
30
31
32
class Solution {
public:
static bool compare(vector<int>& envelope1, vector<int>& envelope2) {
if (envelope1[0] != envelope2[0]) return envelope1[0] < envelope2[0];
return envelope1[1] > envelope2[1];
}
int binarySearch(vector<int>& res, int target) {
int left = 0;
int right = res.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (res[mid] >= target) right = mid;
else left = mid + 1;
}
return left;
}
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(), compare);
vector<int> res;
res.push_back(envelopes[0][1]);
for (int i = 1; i < envelopes.size(); i++) {
if (envelopes[i][1] > res.back()) res.push_back(envelopes[i][1]);
else {
int index = binarySearch(res, envelopes[i][1]);
res[index] = envelopes[i][1];
}
}
return res.size();
}
};