Stacking Colored Paper
InterviewTime limit1sMemory limit128 MB
Given N rectangles with allowed 90-degree rotation, find the longest chain where each sheet fits entirely inside the previous one.
- Level
Medium4 of 10
- Topics
- Dynamic programming, Sorting, Greedy
- Solved
- No attempts yet
Problem
There are several rectangular sheets of colored paper, all with different sizes. You want to stack as many sheets as possible by placing them one at a time.
Each new sheet must be placed on top of the sheet currently at the top of the stack. Both of the following conditions must hold.
- The new sheet must not be larger than the top sheet. No part of it may extend outside the top sheet.
- The sides of the new sheet and the top sheet must be parallel. A sheet may be rotated by 90 degrees.
In the four drawings below, only (B) satisfies both conditions.
 |  |  |  |
| (A) | (B) | (C) | (D) |
A sheet is described by its two side lengths. (3, 5) means a sheet whose side lengths are 3 and 5. If the seven sheets have side lengths (1, 2), (8, 7), (20, 10), (20, 20), (15, 12), (12, 14), (11, 12), one maximum stack is (20, 20), (15, 12), (12, 14), (11, 12), (8, 7), (1, 2).
Given the sheets, compute the maximum number of sheets that can be stacked.
Input
The first line contains N, the number of sheets. Each of the next N lines contains the two side lengths of one sheet, separated by a space.
There are at most 100 sheets, and every side length is a positive integer less than 1000.
Output
Print the maximum number of sheets that can be stacked.