357. Nesting Boxes
A gift shop sells hollow boxes, and each box is described by a pair [width, height]. A box can be placed inside another box only if both its width and its height are strictly smaller than the other box's width and height. Boxes cannot be rotated.
Given the list boxes, return the largest number of boxes that can be nested one inside the next, like a set of wooden dolls, using each box at most once. Boxes may have identical sizes, and identical boxes cannot be nested in each other. With up to a hundred thousand boxes an O(n^2) solution is too slow; aim for O(n log n).
Example 1
- Input:
- boxes = [[2,5],[4,6],[5,9],[5,7],[7,10]]
- Output:
- 4
- Explanation:
One longest chain is [2, 5] inside [4, 6] inside [5, 7] inside [7, 10], so 4 boxes nest.
Example 2
- Input:
- boxes = [[3,3],[3,3]]
- Output:
- 1
- Explanation:
Two identical boxes cannot be nested, so the answer is 1.
Constraints
1 ≤ boxes.length ≤ 105
boxes[i].length == 2
1 ≤ width, height ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)