1186. Russian Doll Envelopes

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). The input is JSON {envelopes}.

Input: JSON {envelopes}.

Output: Integer — the maximum number of nested envelopes.

Examples

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

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

Input: {"envelopes":[[3,5]]}
Output: 1
Explanation: Single envelope.

Constraints

• 1<=n<=10^5

Asked by