diff options
author | Jack Sangdahl <[email protected]> | 2025-01-09 22:29:19 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-09 22:29:19 +0100 |
commit | 8050c7264ba4487a1e64b150633961097382ac5b (patch) | |
tree | 940e0429a5caf113d28a171b2365e79df0af5af4 | |
parent | 2d159f42638f87dfca97a0ab50099b0eef651e5e (diff) | |
download | leetcode-8050c7264ba4487a1e64b150633961097382ac5b.tar.gz leetcode-8050c7264ba4487a1e64b150633961097382ac5b.zip |
354. russian doll envelopes
-rw-r--r-- | russian_doll_envelopes.c | 60 | ||||
-rw-r--r-- | russian_doll_envelopes.cpp | 28 | ||||
-rw-r--r-- | russian_doll_envelopes.py | 33 |
3 files changed, 93 insertions, 28 deletions
diff --git a/russian_doll_envelopes.c b/russian_doll_envelopes.c new file mode 100644 index 0000000..0849180 --- /dev/null +++ b/russian_doll_envelopes.c @@ -0,0 +1,60 @@ +// 354. Russian Doll Envelopes +#include "leetcode.h" + +/* + * you are given a 2d array of integers 'envelopes' where 'envelopes[i] = [w_i, + * h_i]' represents the width and height of an envelope. one envelope can fit + * into another if and only if both the width and height of one envelope are + * greater than the other envelope's width and height. return the maximum number + * of envelopes you can russian doll (ie. put one inside the other). + */ + +int bin_search(int *dp, int start, int end, int target) { + while (start < end) { + int mid = start + (end - start) / 2; + if (dp[mid] == target) + return mid; + else if (dp[mid] > target) + end = mid; + else + start = mid + 1; + } + return start; +} + +int cmp(const void *a, const void *b) { + if ((*(int **)a)[0] == (*(int **)b)[0]) + return (*(int **)b)[1] - (*(int **)a)[1]; + else + return (*(int **)a)[0] - (*(int **)b)[0]; +} + +int maxEnvelopes(int **envelopes, int envelopesSize, int *envelopesColSize) { + qsort(envelopes, envelopesSize, sizeof(int **), cmp); + int *dp = (int *)malloc(envelopesSize * sizeof(int)), ans = 0; + dp[0] = envelopes[0][1]; + for (int i = 1; i < envelopesSize; i++) { + if (envelopes[i][1] > dp[ans - 1]) + dp[ans++] = envelopes[i][1]; + else { + int idx = bin_search(dp, 0, ans, envelopes[i][1]); + dp[idx] = envelopes[i][1]; + if (idx == ans) + ans++; + } + } + free(dp); + return ans; +} + +int main() { + int e1i[4][2] = {{5, 4}, {6, 4}, {6, 7}, {2, 3}}, + e2i[3][2] = {{1, 1}, {1, 1}, {1, 1}}; + struct two_d_arr e1, e2; + two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i); + two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i); + printf("%d\n", maxEnvelopes(e1.arr, e1.row_size, e1.col_size)); // expect: 3 + printf("%d\n", maxEnvelopes(e2.arr, e2.row_size, e2.col_size)); // expect: 1 + two_d_arr_free(&e1); + two_d_arr_free(&e2); +} diff --git a/russian_doll_envelopes.cpp b/russian_doll_envelopes.cpp deleted file mode 100644 index fce0aa3..0000000 --- a/russian_doll_envelopes.cpp +++ /dev/null @@ -1,28 +0,0 @@ -#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() {} diff --git a/russian_doll_envelopes.py b/russian_doll_envelopes.py new file mode 100644 index 0000000..99731e7 --- /dev/null +++ b/russian_doll_envelopes.py @@ -0,0 +1,33 @@ +# 354. Russian Doll envelopesnvelopes +from bisect import bisect_left + +""" +you are given a 2d array of integers 'envelopes' where 'envelopes[i] = [w_i, +h_i]' represents the width and height of an envelope. one envelope can fit +into another if and only if both the width and height of one envelope are +greater than the other envelope's width and height. return the maximum number +of envelopes you can russian doll (ie. put one inside the other). +""" + + +class Solution(object): + def maxenvelopesnvelopes(self, envelopes): + """ + :type envelopes: List[List[int]] + :rtype: int + """ + envelopes.sort(key=lambda x: (x[0], -x[1])) + dp = [] + for _, height in envelopes: + left = bisect_left(dp, height) + if left == len(dp): + dp.append(height) + else: + dp[left] = height + return len(dp) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxenvelopesnvelopes(envelopes=[[5, 4], [6, 4], [6, 7], [2, 3]])) + print(obj.maxenvelopesnvelopes(envelopes=[[1, 1], [1, 1], [1, 1]])) |