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<h_j$ and $w_i<w_j$. 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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.