1691. Maximum Height by Stacking Cuboids Hard

1/**
2 * [1691] Maximum Height by Stacking Cuboids 
3 *
4 * Given n cuboids where the dimensions of the i^th cuboid is cuboids[i] = [widthi, lengthi, heighti] (0-indexed). Choose a subset of cuboids and place them on each other.
5 * You can place cuboid i on cuboid j if widthi <= widthj and lengthi <= lengthj and heighti <= heightj. You can rearrange any cuboid's dimensions by rotating it to put it on another cuboid.
6 * Return the maximum height of the stacked cuboids.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2019/10/21/image.jpg" style="width: 420px; height: 299px;" />
10 * 
11 * Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]
12 * Output: 190
13 * Explanation:
14 * Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
15 * Cuboid 0 is placed next with the 45x20 side facing down with height 50.
16 * Cuboid 2 is placed next with the 23x12 side facing down with height 45.
17 * The total height is 95 + 50 + 45 = 190.
18 * 
19 * Example 2:
20 * 
21 * Input: cuboids = [[38,25,45],[76,35,3]]
22 * Output: 76
23 * Explanation:
24 * You can't place any of the cuboids on the other.
25 * We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.
26 * 
27 * Example 3:
28 * 
29 * Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
30 * Output: 102
31 * Explanation:
32 * After rearranging the cuboids, you can see that all cuboids have the same dimension.
33 * You can place the 11x7 side down on all cuboids so their heights are 17.
34 * The maximum height of stacked cuboids is 6 * 17 = 102.
35 * 
36 *  
37 * Constraints:
38 * 
39 * 	n == cuboids.length
40 * 	1 <= n <= 100
41 * 	1 <= widthi, lengthi, heighti <= 100
42 * 
43 */
44pub struct Solution {}
45
46// problem: https://leetcode.com/problems/maximum-height-by-stacking-cuboids/
47// discuss: https://leetcode.com/problems/maximum-height-by-stacking-cuboids/discuss/?currentPage=1&orderBy=most_votes&query=
48
49// submission codes start here
50
51impl Solution {
52    pub fn max_height(cuboids: Vec<Vec<i32>>) -> i32 {
53        0
54    }
55}
56
57// submission codes end
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62
63    #[test]
64    fn test_1691() {
65    }
66}
67