Each envelope is [width, height]. Envelope A fits inside envelope B only if A is strictly narrower and strictly shorter than B. You can't rotate envelopes.
Write max_envelopes(envelopes: list[list[int]]) -> int: the largest number of envelopes you can nest one inside another.
Examples:
max_envelopes([[4, 5], [4, 7], [2, 3], [7, 8]]) == 3([2,3]in[4,5]in[7,8])max_envelopes([[3, 3], [3, 3]]) == 1max_envelopes([[1, 9], [2, 8], [3, 7]]) == 1
Constraints: 1 <= len(envelopes) <= 100_000, sides between 1 and 10^5. O(n²) is too slow for the tests.
Show hint
sort, then this becomes a longest-increasing-subsequence problem on heights. Think about how to sort ties in width so that two envelopes of equal width can never both be chosen.