Level 1 The longest nest
A storeroom keeps flat cardboard boxes. Each box is [w, h]: a width and a height, both positive integers. Box A goes inside box B only when A is strictly smaller in both dimensions (A.w < B.w and A.h < B.h). Boxes keep the orientation they are listed in: a width is always compared with a width.
A nest is a run of boxes where each one goes inside the next. Write max_nest(boxes) -> int: how many boxes the longest nest holds, counting the outer one. With no boxes the answer is 0.
max_nest([[100, 100], [20, 80], [39, 39]])
# 2: [20,80] or [39,39] fits in [100,100], but neither fits in the other
max_nest([[100, 100], [39, 39], [20, 80], [29, 29], [19, 79], [10, 10]])
# 4: [10,10] in [29,29] in [39,39] in [100,100]
# ([10,10] in [19,79] in [20,80] in [100,100] is another nest of 4)
max_nest([[5, 5], [5, 7], [5, 9]])
# 1: equal widths never nest
Constraints: 0 <= len(boxes) <= 100_000, 1 <= w, h <= 10^9. The same box may be listed more than once. You may reorder or modify boxes.
⭐ Bonus: a speed test with 100,000 boxes earns a star in O(n log n). Comparing every pair of boxes, O(n²), passes every other test but not this one.
Show hint
once the boxes are sorted by width, only the heights matter. Boxes with the same width are the trap: think about how to order them so that you can never pick two of them.