Formatted question description: https://leetcode.ca/all/1691.html

Question

Given n cuboids where the dimensions of the i-th cuboid is cuboids[i] = [width_i, length_i, height_i] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if width_i <= width_j and length_i <= length_j and height_i <= height_j. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

Example 1:

Image text

Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]

Output: 190

Explanation:

Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.

Cuboid 0 is placed next with the 45x20 side facing down with height 50.

Cuboid 2 is placed next with the 23x12 side facing down with height 45.

The total height is 95 + 50 + 45 = 190.

Example 2:

Input: cuboids = [[38,25,45],[76,35,3]]

Output: 76

Explanation:

You can’t place any of the cuboids on the other.

We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.

Example 3:

Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]

Output: 102

Explanation:

After rearranging the cuboids, you can see that all cuboids have the same dimension.

You can place the 11x7 side down on all cuboids so their heights are 17.

The maximum height of stacked cuboids is 6 * 17 = 102.

Constraints:

  • n == cuboids.length
  • 1 <= n <= 100
  • 1 <= width_i, length_i, height_i <= 100

Solution

First, rearrange all the cuboids such that for any cuboids[i], there is cuboids[i][0] <= cuboids[i][1] <= cuboids[i][2]. Then sort all the cuboids according to their widths, lengths and heights.

For any two cuboids cuboids[j] and cuboids[i] where 0 <= j < i < n, cuboids[j] can be placed on cuboids[i] if and only if cuboids[j][0] <= cuboids[i][0] and cuboids[j][1] <= cuboids[i][1] and cuboids[j][2] <= cuboids[i][2]. If this is not the case, then cuboids[j] cannot be placed on cuboids[i] even if the two cubiods are rearranged.

After all the cuboids are rearranged and sorted, use dynamic programming to find the maximum height. Create an array dp of length n such that dp[i] represents the maximum height when cuboids[i] is used. Initially, dp[i] = cuboids[i][2] for all 0 <= i < n. For each cuboid, always use the last dimention since it is the dimension with the maximum value in the cuboid. For each 1 <= i < n, loop over 0 <= j < i. If cuboids[j] can be placed on cuboids[i], then update dp[i] using dp[j] + cuboids[i][2].

In the dynamic programming process, maintain the maximum height. Finally, return the maximum height.

This question is related to 354 Russian Doll Envelopes, expanding from a 2-D issue to 3-D issue.

因为题目允许任意旋转长方体,我们尝试将每个长方体的六个旋转变种都考虑进来。这样总共有6n个cuboids。

因为从下往上堆叠的次序必须是按照长度递减的,和Envelopes题目一样,都需要排序。 所以我们自然会将所有的6n个cuboids按照长度降排列。就像Envelopes题目里把信封按长和宽排序一样,只是从2维到3维,多一层排序条件。

那么对于长度相同的长方体呢?我们可以再按宽度降序排列;对于宽度也相同的长方体,按照高度降序排列。这样,符合要求的堆叠方案必然是这个序列的一个subsequece。注意,并不是说这个序列的任何一个subsequence都是符合要求的堆叠方案。

Code

Python version

# Time:  O(n^2)
# Space: O(n)
    
class Solution(object):
    def maxHeight(self, cuboids):
        """
        :type cuboids: List[List[int]]
        :rtype: int
        """
        for cuboid in cuboids:
            cuboid.sort()
        cuboids.append([0, 0, 0])
        cuboids.sort()
        dp = [0]*len(cuboids)
        for i in xrange(1, len(cuboids)):
            for j in xrange(i):
                if all(cuboids[j][k] <= cuboids[i][k] for k in xrange(3)):
                    dp[i] = max(dp[i], dp[j]+cuboids[i][2])
        return max(dp)

C++ version

class Solution {
public:
    int maxHeight(vector<vector<int>>& cuboids) 
    {
        int n = cuboids.size();
        vector<array<int,4>>p;
        for (int i=0; i<cuboids.size(); i++)
        {
            auto c = cuboids[i];
            p.push_back({c[0], c[1], c[2], i});
            p.push_back({c[0], c[2], c[1], i});
            p.push_back({c[1], c[0], c[2], i});
            p.push_back({c[1], c[2], c[0], i});
            p.push_back({c[2], c[0], c[1], i});
            p.push_back({c[2], c[1], c[0], i});
        }
        sort(p.begin(), p.end());
        vector<int>dp(6*n);
        for (int i=0; i<6*n; i++)
        {
            dp[i] = p[i][2];
            for (int j=0; j<i; j++)
                if (p[j][0]<=p[i][0] && p[j][1]<=p[i][1] && p[j][2]<=p[i][2] && p[j][3]!=p[i][3])
                    dp[i] = max(dp[i], dp[j]+p[i][2]);
        }

        int ret = 0;
        for (int i=0; i<6*n; i++)
            ret = max(ret, dp[i]);        
        return ret;
    }
};

Java version

public class Maximum_Height_by_Stacking_Cuboids {

    class Solution {
        public int maxHeight(int[][] cuboids) {
            if (cuboids == null || cuboids.length == 0) {
                return 0;
            }

            int[] dp = new int[cuboids.length]; // at index=i, longest count

            for(int[] each: cuboids) {
                Arrays.sort(each);
            }

            // sort by: z-axix, then y, then x
            Arrays.sort(cuboids, (a, b) -> a[2] != b[2] ?
                a[2] - b[2]
                : (a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]));

            for(int[] each: cuboids) {
                System.out.println(each[0] + ":" + each[1] + ":" + each[2]);
            }

            for (int bottum = 0; bottum < cuboids.length; bottum++) {
                dp[bottum] = cuboids[bottum][2];

                for (int upper = 0; upper < bottum; upper++) {

                    if (cuboids[upper][0] <= cuboids[bottum][0]
                        && cuboids[upper][1] <= cuboids[bottum][1]
                        && cuboids[upper][2] <= cuboids[bottum][2]) {

                        dp[bottum] = Math.max(dp[bottum], dp[upper] + cuboids[bottum][2]);

                    }
                }
            }

            int maxLen = 1;
            for (int each: dp) {
                maxLen = Math.max(maxLen, each);

            }

            return maxLen;
        }
    }

}

Java

class Solution {
    public int maxHeight(int[][] cuboids) {
        for (int[] cuboid : cuboids)
            Arrays.sort(cuboid);
        Arrays.sort(cuboids, new Comparator<int[]>() {
            public int compare(int[] cuboid1, int[] cuboid2) {
                if (cuboid1[0] != cuboid2[0])
                    return cuboid1[0] - cuboid2[0];
                else if (cuboid1[1] != cuboid2[1])
                    return cuboid1[1] - cuboid2[1];
                else
                    return cuboid1[2] - cuboid2[2];
            }
        });
        int maxHeight = 0;
        int cuboidsCount = cuboids.length;
        int[] dp = new int[cuboidsCount];
        for (int i = 0; i < cuboidsCount; i++) {
            int height = cuboids[i][2];
            maxHeight = Math.max(maxHeight, height);
            dp[i] = height;
        }
        for (int i = 1; i < cuboidsCount; i++) {
            int width = cuboids[i][0], length = cuboids[i][1], height = cuboids[i][2];
            for (int j = i - 1; j >= 0; j--) {
                if (cuboids[j][0] <= width && cuboids[j][1] <= length && cuboids[j][2] <= height) {
                    int totalHeight = dp[j] + height;
                    maxHeight = Math.max(maxHeight, totalHeight);
                    dp[i] = Math.max(dp[i], totalHeight);
                }
            }
        }
        return maxHeight;
    }
}

All Problems

All Solutions