Categories
interview

Box Stacking Problem

Box stacking problem max height of stack possible (can be rotated). The length and breadth of the box beneath should be greater than the one stacked above it.

box-stacking
const getMaxHeight = (boxes) => {
  const rotatedBoxes = [];
  for (let i = 0; i < boxes.length; i++) {
    rotatedBoxes[3 * i] = boxes[i];
    rotatedBoxes[(3 * i) + 1] = {
      width: boxes[i].height,
      breadth: boxes[i].width,
      height: boxes[i].breadth,
      area: boxes[i].height * boxes[i].width
    };
    rotatedBoxes[(3 * i) + 2] = {
      width: boxes[i].breadth,
      breadth: boxes[i].height,
      height: boxes[i].width,
      area: boxes[i].breadth * boxes[i].height
    };
  }
  // Sort in non-increasing order. 
  rotatedBoxes.sort((box1, box2) => box2.area - box1.area);
  const maxStackedHeight = [];
  for (let i = 0; i < rotatedBoxes.length; i++) {
    maxStackedHeight[i] = 0;
    let box = rotatedBoxes[i];
    let prevMaxVal = 0;
    for (let j = 0; j < i; j++) {
      let prev = rotatedBoxes[j];
      if (prev.width > box.width && prev.breadth > box.breadth) {
        prevMaxVal = Math.max(prevMaxVal, maxStackedHeight[j]);
      }
    }
    maxStackedHeight[i] = prevMaxVal + box.height;
  }
  let max = 0;
  for (let i = 0; i < maxStackedHeight.length; i++) {
    max = Math.max(maxStackedHeight[i], max);
  }
  return max;
};

Test

console.log(getMaxHeight([{
width: 1,
breadth: 1,
height: 1,
area: 1,
}, {
width: 2,
breadth: 3,
height: 10,
area: 6,
}, {
width: 2,
breadth: 4,
height: 1,
area: 8,
}]));
// 16

Demo