Nested Container Stacking

HARD40 pts

You are given a collection of rectangular containers, where each container is represented by its dimensions as a pair [width, height]. A container can be placed inside another container if and only if both the width and height of the inner container are strictly smaller than the corresponding dimensions of the outer container.

Your task is to determine the maximum number of containers that can be nested within each other, forming a chain of containers where each container fits snugly inside the next larger one. This is analogous to the classic matryoshka (Russian nesting dolls) concept, but applied to rectangular containers.

Important Constraints:

You cannot rotate containers. Their width and height orientations are fixed.
For one container to fit inside another, both dimensions must be strictly greater (not equal).
Each container can only be used once in the nesting chain.

The goal is to find the longest possible nesting sequence and return the count of containers that can be nested.

Example

Input

containers = [[5,4],[6,4],[6,7],[2,3]]

Output

3

Explanation

The maximum nesting chain has length 3. One valid sequence is: [2,3] fits inside [5,4] which fits inside [6,7]. Container [6,4] cannot extend this chain because while its width (6) equals [6,7]'s width, the width must be strictly smaller for nesting.

Example

Input

containers = [[1,1],[1,1],[1,1]]

Output

1

Explanation

All containers have identical dimensions. Since nesting requires strictly smaller dimensions, no container can fit inside another. The best we can do is select any single container, resulting in a chain length of 1.

Example

Input

containers = [[1,1],[2,2],[3,3],[4,4]]

Output

4

Explanation

Each container is strictly larger than the previous in both dimensions. The complete nesting sequence is: [1,1] → [2,2] → [3,3] → [4,4], giving us the maximum chain length of 4.

Accepted0/0·0% Acceptance

Constraints

1 ≤ containers.length ≤ 10⁵
containers[i].length == 2
1 ≤ width, height ≤ 10⁵

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

containers =

[[5,4],[6,4],[6,7],[2,3]]

Nested Container Stacking

Hints

Nested Container Stacking

Hints