hardDynamic Programming 1DPure DSA~40 min
Nested Capacity Envelopes
Storage tiers each have a width (IOPS budget) and height (capacity). One tier nests inside another only if both dimensions are strictly larger. Find the longest chain of tiers that can be nested one inside the next.
Problem
Given envelopes[i] = [w, h], one envelope fits into another only if both its width and height are strictly smaller. Return the maximum number of envelopes you can nest (a Russian-doll chain).
Input
An array of n pairs [w, h] (1 ≤ n ≤ 10^5, 1 ≤ w, h ≤ 10^5).
Output
An integer: the longest nesting chain length.
Constraints
- 1 ≤ n ≤ 10^5
- Both dimensions must be strictly larger to nest
- Rotation is not allowed
Examples
Example 1
Input
envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output
3
[2,3] → [5,4] → [6,7] nests three deep.
Example 2
Input
envelopes = [[1,1],[1,1],[1,1]]
Output
1
Equal dimensions can't nest, so the chain is length 1.