Skip to content

Instantly share code, notes, and snippets.

@fluffywaffles
Created October 30, 2015 04:56
Show Gist options
  • Save fluffywaffles/931af7e39b9458c05632 to your computer and use it in GitHub Desktop.
Save fluffywaffles/931af7e39b9458c05632 to your computer and use it in GitHub Desktop.
// Array.sort(byVolume)
function byVolume (a, b) {
va = a[0] + a[1] + a[2]
vb = b[0] + b[1] + b[2]
if (va > vb)
return -1
else if (vb > va)
return 1
return 0
}
// Answer the question
function maxNestedBoxes (boxes) {
var size = boxes.length
, i = size - 1
, memo = []
memo[size] = 0
function nextFeasible (i) {
var box = boxes[i]
for (; i < size; i++) {
if (box[0] > boxes[i][0]
&& box[1] > boxes[i][1]
&& box[2] > boxes[i][2]) {
return i
}
}
return i
}
for(; i >= 0; i--) {
memo[i] = Math.max(1 + memo[nextFeasible(i)],
memo[i + 1])
}
return memo
}
var test = [ [ 6, 6, 6 ], [ 1, 2, 3 ], [ 1, 1, 1 ] ]
test.sort(byVolume)
console.log(maxNestedBoxes(test))
var test2 = [ [ 3, 4, 1 ], [ 2, 2, 2 ], [ 2, 1, 1 ], [ 3, 3, 3 ] ]
test2.sort(byVolume)
console.log(maxNestedBoxes(test2))
var test3 = [ [ 7, 7, 7 ], [ 1, 1, 1 ], [ 1, 2, 3 ], [ 2, 3, 4 ], [ 3, 4, 5 ] ]
test3.sort(byVolume)
console.log(maxNestedBoxes(test3))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment