602. Russian Doll Envelopes

Description

Give a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

Find the maximum number of nested layers of envelopes.

Example

Example 1:

Input：[[5,4],[6,4],[6,7],[2,3]]

Output：3

Explanation：

the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input：[[4,5],[4,6],[6,7],[2,3],[1,1]]

Output：4

Explanation：

the maximum number of envelopes you can Russian doll is 4 ([1,1] => [2,3] => [4,5] / [4,6] => [6,7]).

思路：

先将宽度正序排之后，高度逆序排（这个很关键），然后求高度的最长上升子序列，同76题即为一样的。另外注意用Lambda函数排序的写法。

代码：