Nesting Boxes By Both Sides
Each box has a width and a height. Box A fits inside box B when A is
STRICTLY smaller in BOTH dimensions. Print the largest number of boxes that can be
nested one inside another.
(5,4) (6,4) (6,7) (2,3) -> 3 (2,3) inside (5,4) inside (6,7)
Rotation is not allowed, so a box of (1,2) never fits inside (2,1).
With one dimension this is problem #452 directly. Two dimensions look like they need a two-dimensional table, and they do not: sorting removes one of them.
Sort by width ascending. Then any valid nesting is an increasing subsequence of the HEIGHTS, because the widths are already in order. So the answer is the longest strictly increasing subsequence of the height sequence.
The tie-break is the trap, and it is the reason this problem is worth writing. Boxes with EQUAL width cannot nest, whatever their heights. Sorting equal widths by ascending height would let the height sequence increase across them and count a nesting that is illegal.
So sort equal widths by DESCENDING height. Then within a group of equal widths the heights fall, so no increasing subsequence can pick two of them, and the restriction is enforced by the ordering rather than by a check.
(4,5) (4,6) is in the tests for exactly this: the answer must not treat those two
as nestable.