Skip to content

Instantly share code, notes, and snippets.

@chrisc24
Created April 23, 2012 14:04
Show Gist options
  • Save chrisc24/2471088 to your computer and use it in GitHub Desktop.
Save chrisc24/2471088 to your computer and use it in GitHub Desktop.
Boxes Within Boxes Spoiler!!!
For Each Box:
Compare to all other boxes,
Create a list of boxes that could fit inside it (one layer only)
(N^2),
For each box, create a data structure that includes the box itself, an int bestCount and another box bestBox
Sort the boxes by size (N Log N).
Iterate through the boxes started with the smallest
If a box doesn't contain any boxes give it bestCount 1, and bestbox Null
If a box can contain other boxes look at those. Pick the one with the highest bestCount.
That is your bestBox, your bestCount is that boxes's bestcount + 1.
Those values are guarunteed to be filled in because any box that can fit inside it is smaller and therefore already filled in.
(This part is N^2 again).
Once you have calculated the bestcount and bestbox for all boxes go through them and find the one(s) with the best count. Go down through the bestBox and you have your chain. (O(N) + O(N) for this part)
N^2 + NLogN + N^2 + N + N = N^2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment