aboutsummaryrefslogtreecommitdiff
path: root/max_height_stacking_cuboids.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_height_stacking_cuboids.py')
-rw-r--r--max_height_stacking_cuboids.py43
1 files changed, 43 insertions, 0 deletions
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],
+ ]
+ )
+ )