Maximize Boxes Stored Through One Entrance
A warehouse is a row of n rooms accessed through a single entrance at the left; heights[i] is room i's ceiling. You have boxes with heights boxes[j]. Boxes are pushed in from the entrance and slide right; a box cannot pass through any room with a ceiling lower than the box (equal heights pass), and each room stores at most one box. Boxes may be inserted in any order you choose, and you may discard boxes. Maximize the number of boxes stored.
maxBoxes([5, 3, 3, 4, 1], [1, 2, 2, 3, 4]) -> 5 maxBoxes([1, 2, 2, 3, 4], [3, 4, 1, 2]) -> 1 // height-1 entrance chokes everything
Hints
Hint 1
A room's real ceiling is the minimum of every ceiling on the way in: usable[i] = min(heights[0..i]), a non-increasing prefix min.
Hint 2
Sort boxes ascending and walk rooms deepest-first (most constrained): if the smallest unused box fits the current room's usable ceiling, place it. An exchange argument shows smallest-into-deepest never loses a box.