aboutsummaryrefslogtreecommitdiff
path: root/russian_doll_envelopes.cpp
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /russian_doll_envelopes.cpp
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'russian_doll_envelopes.cpp')
-rw-r--r--russian_doll_envelopes.cpp28
1 files changed, 28 insertions, 0 deletions
diff --git a/russian_doll_envelopes.cpp b/russian_doll_envelopes.cpp
new file mode 100644
index 0000000..fce0aa3
--- /dev/null
+++ b/russian_doll_envelopes.cpp
@@ -0,0 +1,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() {}