Nesting Boxes
Each item of boxes is [width, height]. Box A can go inside box B only if A is strictly narrower and strictly shorter: widthA < widthB and heightA < heightB. Boxes cannot be rotated. A box can hold one box directly, which may itself hold another, and so on, forming a chain.
Return the largest number of boxes that can form one chain. A single box is a chain of length 1, and an empty list gives 0. Two boxes with the same width or the same height never nest, whichever way round.
Example 1
[2, 3] fits in [5, 4], which fits in [6, 7]. [6, 4] cannot join: it is as tall as [5, 4] and as wide as [6, 7].
Example 2
Identical boxes never nest, so the longest chain is a single box.
Constraints
0 <= len(boxes) <= 601 <= width, height <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Sorting and searching problems
- Outline of the SkylineHard
- Shorten the Longest GapHard
- Two Teams of Equal SizeHard
- Height CheckerBeginner
- Kth Largest ElementBeginner
- Kth Smallest Distinct ValueBeginner
- Maximum Product of Two ElementsBeginner
- Median of the ListBeginner