Practice/Amazon/Leetcode 1691. Maximum Height by Stacking Cuboids

Leetcode 1691. Maximum Height by Stacking Cuboids

CodingOptional

Problem

You are given a collection of rectangular boxes, where each box has three dimensions: width, length, and height. You can rotate any box to use any face as its base, meaning you can choose which dimension becomes the height.

Your goal is to build the tallest possible tower by stacking some or all of these boxes. However, there's a stacking rule: you can only place box A on top of box B if all three dimensions of box A are strictly less than or equal to the corresponding dimensions of box B when both boxes are oriented the same way.

More formally, if box A has dimensions (wA, lA, hA) and box B has dimensions (wB, lB, hB), then A can be placed on top of B only if wA ≤ wB AND lA ≤ lB AND hA ≤ hB.

Return the maximum possible height of the tallest tower you can build.

Requirements

You may rotate any box to choose which dimension serves as the height
When stacking, all three dimensions of the upper box must be ≤ the corresponding dimensions of the lower box
You don't have to use all boxes; select an optimal subset
Return the maximum achievable total height (sum of heights of selected boxes)

Constraints

1 ≤ boxes.length ≤ 100
1 ≤ width, length, height ≤ 100
All dimensions are positive integers

Examples

Example 1:

` Input: boxes = [[50,45,20],[95,37,53],[45,23,12]] Output: 190 Explanation:

Normalize box 0 to [20,45,50]
Normalize box 1 to [37,53,95]
Normalize box 2 to [12,23,45] After sorting, we can stack boxes in order that respects dimension constraints. The optimal stacking uses boxes 0 and 1 with heights 95+95=190. `

Example 2:

Input: boxes = [[38,25,45]] Output: 45 Explanation: Only one box. Orient it so the largest dimension (45) is the height.

Example 3:

Input: boxes = [[7,11,17],[7,17,11],[11,7,17]] Output: 51 Explanation: These are different orientations of similar boxes. Stack all three boxes, each contributing 17 to the height, for a total of 51.