Tallest Stack of Rotatable Cuboids
You stack rack modules (cuboids) into a tower. A module can sit on another only if its width, depth, and height each fit within the one below. Modules may be rotated. Maximize the tower height.
Problem
Given an array cuboids where cuboids[i] = [w, l, h], you may rotate each cuboid so its dimensions are reordered. Cuboid j can be placed on cuboid i if width_j <= width_i, length_j <= length_i, and height_j <= height_i (using the chosen orientations). Return the maximum total height of a stack.
Input
An array cuboids of [width, length, height] triples.
Output
An integer: the maximum stack height.
Constraints
- 1 <= cuboids.length <= 100
- 1 <= dimension values <= 10000
Examples
Example 1
Input
cuboids = [[50,45,20],[95,37,53],[45,23,12]]
Output
190
Stacking all three in good orientations reaches height 190.
Example 2
Input
cuboids = [[38,25,45],[76,35,3]]
Output
76
Only one cuboid can sit on a base here, giving height 76.