Filling Bookcase Shelves
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
You are given books, where books[i] = [thickness_i, height_i], and an integer shelfWidth.
Place the books on shelves in their given order: the first shelf takes the first few books, the next shelf the next few, and so on. The books on one shelf must have a total thickness of at most shelfWidth. A shelf is as tall as its tallest book, and the bookcase is as tall as all its shelves together.
Return the minimum possible total height of the bookcase.
Examples
Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4 Output: 6
Shelf 1: the first book (height 1). Shelf 2: the two books of height 3 (width 4). Shelf 3: the last four books (width 4, height 2). 1 + 3 + 2 = 6.
Input: books = [[1,3],[2,4],[3,2]], shelfWidth = 3 Output: 6
The first two books share a shelf of height 4; the third, 3 thick, needs a shelf of its own of height 2.
Input: books = [[1,1],[1,9],[1,9]], shelfWidth = 2 Output: 10
Filling the first shelf fully puts the short book beside a tall one (9), leaving the last book alone (9): 18. Putting the short book alone (1) and the two tall ones together (9) gives 10.
Constraints
- 1 <= len(books) <= 1000
- 1 <= thickness_i <= shelfWidth <= 1000
- 1 <= height_i <= 1000
Approaches
- Try every way to break the shelves — time O(2^n), space O(n)
Follow-up
If the books could be reordered, sorting them by height and grouping neighbors would be the natural start, but the problem becomes a two-dimensional packing question with no simple exact DP. The fixed order is what makes the prefix DP exact.
Related problems
Start free on Cariara · Coding problems · System design studio
