Tray stacking yard
HardOnline Assessment
Find how few nests a warehouse needs to store all of its open crates.
A warehouse holds open-top crates of different sizes. Crate i has width widths[i] and depth depths[i]; both are lowercase letters, and a letter earlier in the alphabet is a smaller size ("a" is the smallest, "z" the largest).
A crate A fits inside crate B only if A is strictly narrower than B and strictly shallower than B. If the widths are equal, or the depths are equal, it does not fit, and crates are never rotated.
A nest is a group of crates that can be arranged one inside the next, so that every crate in the group fits inside the following one (a crate on its own is a nest too). Every crate must be stored in exactly one nest.
Input: widths and depths, two strings of the same length where widths[i] and depths[i] describe crate i.
Output: the smallest number of nests that can hold every crate. With no crates, return 0.
The warehouse can hold thousands of crates, so comparing every pair of crates will be too slow.
Example 1
- Input:
- ["abc","abc"]
- Output:
- 1
- Explanation
- The crates are (a,a), (b,b), (c,c). Each fits inside the next, so one nest holds all three.
Example 2
- Input:
- ["aab","abb"]
- Output:
- 2
- Explanation
- The crates are (a,a), (a,b) and (b,b). (a,a) fits inside (b,b), since it is strictly narrower and strictly shallower. (a,b) is as wide as (a,a) and as deep as (b,b), so it fits inside neither and nothing fits inside it. The best packing is the nest {(a,a), (b,b)} plus (a,b) alone: 2 nests.
Example 3
- Input:
- ["aabbcc","bababa"]
- Output:
- 4
- Explanation
- The crates are (a,b), (a,a), (b,b), (b,a), (c,b), (c,a). The only nestings are (a,a) inside (b,b) or (c,b), and (b,a) inside (c,b). So the crates (a,b), (b,b), (c,b), (c,a) can never share a nest with one another: any two of them tie on width or on depth, or are ordered the wrong way. That forces at least 4 nests, and {(a,a),(b,b)}, {(b,a),(c,b)}, {(a,b)}, {(c,a)} achieves it.
Constraints
widths.length == depths.length0 <= widths.length <= 12,000- every character of
widthsanddepthsis a lowercase letter; a letter that comes earlier in the alphabet means a smaller size