Arrange Items on Shelves to Minimize Total Height
Place items in order onto a sequence of fixed-width shelves. Each shelf holds a prefix of the remaining items up to a width limit; the shelf's height is its tallest item. Minimize the stacked height of all shelves.
Problem
Given books where books[i] = [thickness, height] that must be placed left to right, and a shelf width shelfWidth, each shelf holds a contiguous run of books whose total thickness <= shelfWidth and takes height equal to the tallest book on it. Return the minimum possible total height of the bookcase.
Input
A list books of [thickness, height] and an integer shelfWidth.
Output
An integer: the minimum total bookcase height.
Constraints
- 1 <= books.length <= 1000
- 1 <= thickness[i] <= shelfWidth <= 1000
- 1 <= height[i] <= 1000
Examples
Example 1
Input
books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
Output
6
An optimal shelving yields total height 6.
Example 2
Input
books = [[1,3],[2,4],[3,2]], shelfWidth = 6
Output
4
All three fit on one shelf of height 4.