Given a list of envelopes where each envelope has a width and a height, return the maximum number of envelopes you can nest inside one another. Pattern focus: LIS. Sort carefully first, then reduce the problem to a one-dimensional increasing subsequence on heights.
envelopes = array of [width, height] pairs
maximum number of nested envelopes
Example 1:
Input:
envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output:
3
Explanation:
One nesting chain is [2,3] -> [5,4] -> [6,7].
Example 2:
Input:
envelopes = [[1,1],[1,1],[1,1]]
Output:
1
Explanation:
Equal-width envelopes cannot be nested.
Example 3:
Input:
envelopes = [[2,3],[5,4],[6,7],[6,4]]
Output:
3
Explanation:
A valid chain is [2,3] -> [5,4] -> [6,7].