Russian Doll Envelopes
You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.
Return the maximum number of envelopes you can Russian doll (put one inside the other).
Note: You cannot rotate an envelope.
Examples
Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Input: [[1,1],[1,1],[1,1]]
Output: 1
Hints
Sort the envelopes by width in ascending order. If two envelopes have the same width, sort them by height in descending order to prevent them from being included in the same sequence.
After sorting, the problem reduces to finding the longest increasing subsequence (LIS) based on the height dimension only, since widths are already in non-decreasing order.
Use a dynamic programming approach or a greedy algorithm with binary search to efficiently compute the LIS on the height array, which will give the maximum number of envelopes that can be Russian dolled.
Russian Doll Envelopes
You are given a 2D array of integers `envelopes` where `envelopes[i] = [wi, hi]` represents the width and height of an envelope.