1775: 俄罗斯套娃信封
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:34
Solved:8
Description
给你一个 n对整数的二维数组 nums ,其中 nums[i] = [wi,hi] ,表示第 i 个信封的宽度wi和高度hi。 当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算 最多能有多少个 信封可以组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。注意:不允许旋转信封
如有4个信封,其二维数组nums= [[5,4][6,4][6,7][2,3]] 。最多套娃信封的个数为 3个。从小到大为: [2,3] => [5,4] => [6,7]。
Input
输入第一行为一个整数 n (1 ≤ n ≤100000)。
接下来的 n 行, 第 i+1 行包含两个整数 wi 和 hi。 wi表示第 i第 i 个信封的宽度,hi 表示第 i 个信封的高度 ( 1 ≤ wi,hi ≤100000)。
Output
输出一个整数,表示最多能有多少个信封,可以组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。注意:不允许旋转信封。
Sample Input Copy
4
5 4
6 4
6 7
2 3
Sample Output Copy
3
HINT
1 ≤ n ≤100000
1 ≤ wi,hi ≤100000