Created
April 23, 2012 14:04
-
-
Save chrisc24/2471088 to your computer and use it in GitHub Desktop.
Boxes Within Boxes Spoiler!!!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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