Loading...
Loading...
Loading...
There are n boxes, each with a width and a height. One box fits inside another only if both its width and its height are strictly smaller. Boxes cannot be turned. Print the greatest number of boxes in one nested chain.
Example 1
Input
5 5 4 6 4 6 7 2 3 1 1
Output
4
1 1, 2 3, 5 4, 6 7 is a chain of four.
Example 2
Input
3 2 2 2 2 2 2
Output
1
Try the problem first. Open one hint at a time.
Sort the boxes by width ascending and, for equal widths, by height descending.
Then the answer is the longest strictly increasing subsequence of the heights.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor