1
$\begingroup$

I am given a set of 3D boxes {$B_1$, $B_2$...$B_n$} and each box have length, width and height. But these values are interchangeable since I can rotate the box. I need to find out the maximum sequence of nested boxes.

I have tried this problem using sort. But I still get stuck. I used built in sort function to sort all boxes by length in ascending order. I read the reference about this question and learned that people used radix sort. I have know idea how radix sort is applied here because all sorts I am familiar is comparison sort.

$\endgroup$
0
$\begingroup$

One solution that comes to mind is to first build a directed graph where every vertex represents a vertex. An edge goes from Box A to Box B if B fits into A. One can easily verify that this graph contains no cycles. A maximum sequence of nested boxes is equivalent to the longest path in this directed acyclic graph. A longest path in a DAG can be found by using a topological sort on the graph.

This surely is a bit overkill and is probably also not the most efficient solution ($O(n^2)$ for building the graph).

$\endgroup$
  • $\begingroup$ Good algorithm. But in this question the boxes can be rotated. I think comparing boxes is more complicated than $O(n^2)$ $\endgroup$ – hck007 Oct 14 at 15:32
  • $\begingroup$ Well you can check in constant time if one box fits into another. That is all you need to build the graph. Topological sort can be done in linear time in the size of the graph. $\endgroup$ – rex123 Oct 14 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.