Filling Bookcase Shelves

Problem Description

You are given an array books where books[i] = [thickness_i, height_i] indicates the thickness and height of the i-th book. You are also given an integer shelfWidth. We want to place these books in order onto bookcase shelves that have a total width shelfWidth. We choose some of the books to place on this shelf such that the sum of their thickness is less than or equal to shelfWidth, then build another level of the shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place. Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Key Insights

• The order of books must be preserved when placing them on shelves.
• Each shelf can hold books as long as their combined thickness does not exceed shelfWidth.
• The height of each shelf is determined by the tallest book placed on that shelf.
• The problem can be approached using dynamic programming to find the minimum height of the bookshelf.

Space and Time Complexity

Time Complexity: O(n^2) where n is the number of books, as we may need to evaluate the placement of each book against all previous books for each shelf. Space Complexity: O(n) for the dynamic programming array that stores the minimum height at each book index.

Solution

To solve the problem, we can use a dynamic programming approach. We maintain an array dp where dp[i] represents the minimum height of the bookshelf when considering the first i books. We initialize dp[0] to 0 (no books means no height). For each book, we iterate backwards to find the maximum height of books that can fit on the current shelf without exceeding the shelf width. We update the dp array based on the maximum height of the books placed on each shelf.

The algorithmic approach involves:

1. Initializing the dp array.
2. Iterating through each book and determining how many books can fit on the current shelf.
3. Updating the dp array with the minimum height based on previous calculations.

Code Solutions