Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 8 / d

Sort the two dimension vectors separately into ascending order, $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$. Then return true exactly when $a_i<b_i$ for every $i$. Sorting costs $O(d\log d)$ and the coordinate comparisons cost $O(d)$.

Sufficiency follows by matching corresponding ranks and translating that rank matching back to the original axes. For necessity, suppose $a_k\ge b_k$ for some $k$. The $d-k+1$ dimensions $a_k,\dots ,a_d$ must all be assigned to strictly larger target dimensions. None of the first $k$ sorted target dimensions is large enough, leaving at most $d-k$ eligible slots. The pigeonhole principle gives a contradiction. This proves the sorted-coordinate criterion for box containment, including ties: equality fails the required strict fit.

Read “subsequence” in its usual sense: selected indices increase in the given input order. First sort each box's dimension vector, in $O(nd\log d)$ total time. Let $F[j]$ be the maximum number of boxes in a fitting subsequence ending at index $j$. Process $j=1,\dots ,n$ and computeThe last selected box before $j$, if any, supplies exactly one of these candidates; conversely an optimal candidate subsequence can be extended by $j$. Induction on $j$ proves the box nesting recurrence. Store a maximizing predecessor index and reconstruct from an index maximizing $F[j]$. For $n=0$, return the empty subsequence.

There are $O(n^2)$ candidate pairs, each requiring $O(d)$ coordinate comparisons. Hence $O(nd\log d+n^{2}d)$ running time and $O(nd+n)$ storage suffice, including sorted vectors, table entries and reconstruction pointers. It is unnecessary to store every fitting pair.

If “subsequence” was intended to allow arbitrary reordering, build the containment Directed acyclic graph instead: include every fitting ordered pair, then find its longest chain. Strict increase of the smallest sorted dimension gives a topological sorting by that dimension. The same pair-testing bound applies, but the index restriction must then be removed. These two interpretations differ: input boxes $(3,3),(2,2)$ have a longest order-preserving subsequence of one box, but an unrestricted nesting chain of two.