aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-14 21:49:18 -0700
committerJack Sangdahl <[email protected]>2024-11-14 21:49:18 -0700
commit6e0dc08f19d42225935112c849d66db2a5ea63c8 (patch)
tree67d8579f5c6001089591825024680f3c093181eb
parentbaa5c34da7ce05e3cb2006bd04b040fa7da22dce (diff)
downloadleetcode-6e0dc08f19d42225935112c849d66db2a5ea63c8.tar.gz
leetcode-6e0dc08f19d42225935112c849d66db2a5ea63c8.zip
1691. maximum height by stacking cuboids
-rw-r--r--max_height_stacking_cuboids.c74
-rw-r--r--max_height_stacking_cuboids.py43
2 files changed, 117 insertions, 0 deletions
diff --git a/max_height_stacking_cuboids.c b/max_height_stacking_cuboids.c
new file mode 100644
index 0000000..22417a4
--- /dev/null
+++ b/max_height_stacking_cuboids.c
@@ -0,0 +1,74 @@
+// 1691. Maximum Height by Stacking Cuboids
+#include "leetcode.h"
+
+/*
+ * given 'n' cuboids where the dimensions of the i'th cuboid is 'cuboids[i] =
+ * [width_i, length_i, height_i]' (0-indexed). choosee a subset of 'cuboids' and
+ * place them on each other. you can place cuboid 'i' on cuboid 'j' if 'width_i
+ * <= width_j', and similarily for length and height. you can rearrange any
+ * cuboid's dimensions by rotating it to put it on another cuboid. return the
+ * maximum height of the stacked 'cuboids'.
+ */
+
+int cmp_len(const void *a, const void *b) {
+ int aa = *(int *)a, bb = *(int *)b;
+ return aa > bb ? 1 : -1;
+}
+
+int cmp_box(const void *a, const void *b) {
+ int *aa = *(int **)a, *bb = *(int **)b;
+ if (aa[2] > bb[2])
+ return 1;
+ if (aa[2] < bb[2])
+ return -1;
+ else {
+ if (aa[1] > bb[1])
+ return 1;
+ if (aa[1] < bb[1])
+ return -1;
+ else {
+ if (aa[0] > bb[0])
+ return 1;
+ if (aa[0] < bb[0])
+ return -1;
+ else
+ return 0;
+ }
+ }
+}
+
+bool check(int *bottom, int *top) {
+ return top[2] <= bottom[2] && top[1] <= bottom[1] && top[0] <= bottom[0]
+ ? false
+ : true;
+}
+
+int maxHeight(int **cuboids, int cuboidsSize, int *cuboidsColSize) {
+ for (int i = 0; i < cuboidsSize; i++)
+ qsort(cuboids[i], 3, sizeof(int), cmp_len);
+ qsort(cuboids, cuboidsSize, sizeof(cuboids[0]), cmp_box);
+ int *arr = (int *)malloc(cuboidsSize * sizeof(int)), max = arr[0];
+ for (int i = 1; i < cuboidsSize; i++) {
+ for (int j = 0; j < i; j++)
+ if (check(cuboids[i], cuboids[j]))
+ arr[i] = fmax(arr[i], arr[j] + cuboids[i][2]);
+ max = fmax(max, arr[i]);
+ }
+ free(arr);
+ return max;
+}
+
+int main() {
+ int c1i[3][3] = {{50, 45, 20}, {95, 37, 53}, {45, 23, 12}},
+ c2i[2][3] = {{38, 25, 45}, {76, 35, 3}},
+ c3i[6][3] = {{7, 11, 17}, {7, 17, 11}, {11, 7, 17},
+ {11, 17, 7}, {17, 7, 11}, {17, 11, 7}};
+ struct two_d_arr c1, c2, c3;
+ two_d_arr_init(&c1, 3, 3, c1i);
+ two_d_arr_init(&c2, 2, 3, c2i);
+ two_d_arr_init(&c3, 6, 3, c3i);
+ printf("%d\n", maxHeight(c1.arr, c1.row_size, c1.col_size)); // expect: 190
+ printf("%d\n", maxHeight(c2.arr, c2.row_size, c2.col_size)); // expect: 76
+ printf("%d\n", maxHeight(c3.arr, c3.row_size, c3.col_size)); // expect: 102
+ two_d_arr_free(&c1), two_d_arr_free(&c2), two_d_arr_free(&c3);
+}
diff --git a/max_height_stacking_cuboids.py b/max_height_stacking_cuboids.py
new file mode 100644
index 0000000..2d095e1
--- /dev/null
+++ b/max_height_stacking_cuboids.py
@@ -0,0 +1,43 @@
+# 1691. Maximum Height by Stacking Cuboids
+
+"""
+given 'n' cuboids where the dimensions of the i'th cuboid is 'cuboids[i] =
+[width_i, length_i, height_i]' (0-indexed). choosee a subset of 'cuboids' and
+place them on each other. you can place cuboid 'i' on cuboid 'j' if 'width_i
+<= width_j', and similarily for length and height. you can rearrange any
+cuboid's dimensions by rotating it to put it on another cuboid. return the
+maximum height of the stacked 'cuboids'.
+"""
+
+
+class Solution(object):
+ def maxHeight(self, cuboids):
+ """
+ :type cuboids: List[List[int]]
+ :rtype: int
+ """
+ cuboids = [[0, 0, 0]] + sorted(map(sorted, cuboids))
+ dp = [0] * len(cuboids)
+ for i in range(1, len(cuboids)):
+ for j in range(i):
+ if all(cuboids[j][k] <= cuboids[i][k] for k in range(3)):
+ dp[i] = max(dp[i], dp[j] + cuboids[i][2])
+ return max(dp)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxHeight(cuboids=[[50, 45, 20], [95, 37, 53], [45, 23, 12]]))
+ print(obj.maxHeight(cuboids=[[38, 25, 45], [76, 35, 3]]))
+ print(
+ obj.maxHeight(
+ cuboids=[
+ [7, 11, 17],
+ [7, 17, 11],
+ [11, 7, 17],
+ [11, 17, 7],
+ [17, 7, 11],
+ [17, 11, 7],
+ ]
+ )
+ )