Deployment Rack Packing
A deployment team packs identical server rack units into racks. Each unit is a pair [width, height] where width is how many rack columns it occupies and height is its height in rack units (RU).
The units are handed to the packer in a fixed order and must be placed in that exact order from left to right onto shelves, top to bottom. A unit cannot be reordered, rotated, or skipped.
Rules:
- Each shelf has a fixed
rackWidthof usable columns. - On one shelf, units are placed left to right; the combined width of the units on a shelf must never exceed
rackWidth. - A shelf's height is the height of its tallest unit.
- Shelves stack vertically: the total height of the rack is the sum of every shelf's height.
Return the minimum possible total rack height after packing all units.
Examples
Input: [[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]],4]
Output: 6
Input: [[[1,1]],1]
Output: 1
Hints
Process the units left to right. At each unit, decide where the shelf that holds it starts: this unit either continues the current shelf or begins a new shelf. Model this as a prefix DP over unit indices.
Define `dp[i]` = minimum total height to pack the first `i` units. Recurrence: for the shelf ending at unit `i-1`, let it start at some `j`; the shelf must fit units `j..i-1` within `rackWidth`, and its height is the max height in that window.
Try every valid shelf start `j` going backwards from `i-1` while the accumulated width stays within `rackWidth`. Update `dp[i] = min(dp[i], dp[j] + maxHeight(units[j..i-1]))`. This runs in O(n^2) worst case, which fits n up to 1000.
Related Problems
Deployment Rack Packing
A deployment team packs identical server rack units into racks. Each unit is a pair `[width, height]` where `width` is how many rack columns it occupies and `height` is its height in rack units (RU).