Russian doll envelopes: most envelopes nested inside each other

Each envelope has a width and a height. One envelope fits inside another when both its width and its height are strictly smaller. Envelopes cannot be rotated. Return the largest number of envelopes you can nest one inside the next.

Interface

Unless you agree on a different interface with the interviewer, assume:

• max_envelopes(envelopes: list[list[int]]) -> int — each envelope is [width, height].

Example

max_envelopes([[5,4], [6,4], [6,7], [2,3]])         ->  3    # [2,3] in [5,4] in [6,7]
max_envelopes([[1,1], [1,1], [1,1]])                ->  1
max_envelopes([[4,5], [4,6], [6,7], [2,3], [1,1]])  ->  4    # [1,1] [2,3] [4,5] [6,7]

Constraints

• 1 <= len(envelopes) <= 10^5; widths and heights are in [1, 10^5].

Clarifying questions

• Is "fits" strict in both dimensions?
• May envelopes be rotated?
• Do we need the chain itself or only its length?

What a strong answer covers

• The O(n^2) DP over envelopes sorted by width, as a starting point.
• The O(n log n) solution: sort by width ascending and, for equal widths, by height descending; then the answer is the longest strictly increasing subsequence of the heights, found with patience sorting and binary search.
• Why the descending tie-break matters: it stops two envelopes of the same width from both being counted.
• Tests: all equal, equal widths with different heights, a single envelope, already sorted input.

Follow-ups

• Return the nested chain, not only its length.
• Allow rotation.
• Boxes in three dimensions. Why does the LIS trick no longer work directly?