507. Russian Doll Envelopes (BS + Greedy)

Given envelopes as [width, height] pairs, one envelope fits inside another only if both its width and height are strictly greater. Return the maximum number of envelopes you can nest (Russian-doll style). Sort by width ascending and, for equal widths, height descending, then find the longest increasing subsequence on heights. Input: a JSON array of [width, height] pairs.

Input: A JSON array of [width, height] pairs.

Output: Integer — the maximum nested count.

Examples

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: [2,3] -> [5,4] -> [6,7].

Input: [[1,1],[1,1],[1,1]]
Output: 1
Explanation: Equal envelopes cannot nest.

Input: [[4,5]]
Output: 1
Explanation: Single envelope.

Constraints

• 0<=n<=10^5
• 1<=width,height<=10^5

Asked by