# Fastest algorithm to compute maximum number of boxes that can fit inside each other

Given $$n$$ rectangles with widths $$w_1,w_2,...,w_n$$ and heights $$h_1, ..., h_n$$. A rectangle $$i$$ fits inside $$j$$ if and only if $$h_i and $$w_i. We are interested in the maximum $$k$$ such that there exist rectangles $$i_1, i_2, ..., i_k$$ such that $$i_1$$ fits inside $$i_2$$, $$i_2$$ fits inside $$i_3$$, and so on until $$i_k$$.

For the rectangle case, there is a pretty simple algorithm where we sort the elements in increasing order of widths, and when there are ties on widths, in descending order of height. Then find the Longest increasing subsequence (in $$O(n\log n)$$ time) in the sorted array in terms of heights and this solution corresponds to the maximum number of rectangles that can be fit inside each other.

My question, is there a similar approach for the $$3D$$ boxes (with length, widths, and heights) or in general in a fixed dimension $$d$$? There is an $$O(n^2)$$ time algorithm where you build a DAG on the boxes and find the longest path, but I am interested in whether the $$O(n\log n)$$ approach generalizes in higher dimension.

• If I remember correctly, that's an exercise in Cormen-Leiserson-Rivest-Stein. Dec 25, 2021 at 12:39
• @Gamow the 3d case or the 2d case? Happen to remember which chapter? Dec 25, 2021 at 20:21