Problem Breakdown
We are given a sequence of books where each book has a specific thickness and height. We need to stack these books onto shelves with a fixed maximum total width (shelf_width). The key constraints are:
- Order Preservation: Books must be placed in the exact order they appear in the input list (contiguous segments).
- Shelf Height Rule: A shelf’s height is determined by the tallest book on it, regardless of how many books fit horizontally.
- Objective: Minimize the total vertical space used by stacking all shelves sequentially until no more books remain.
Inputs: books (List[List[int]]), shelf_width (int).
Output: Integer representing minimum total height.
Implicit Constraints & Edge Cases:
- Books cannot be skipped or reordered; we must partition the array into contiguous subarrays.
- If a single book’s thickness exceeds
shelf_width, it is impossible per constraints, but given problem guarantees (books[i][0] <= shelf_width), this won’t happen. - Empty input isn’t possible due to constraints ().
Intuition
A brute-force approach would try every possible way to split the books into shelves (partitioning a sequence of length can have up to partitions), leading to exponential time complexity. This is insufficient for .
However, this problem exhibits optimal substructure and overlapping subproblems, characteristic of Dynamic Programming (DP).
- To solve the problem for
nbooks, we need to know the minimum height required to place the firstibooks. Let’s call this statedp[i]. - When considering book at index
i, we have two choices: either start a new shelf with just this book (or extend an existing one), or append it to a previous group on the current shelf. - Since shelves are filled left-to-right, when calculating for book
ias part of a new shelf ending ati, we can look back fromi-1down to find all valid contiguous groups that fit withinshelf_width.
Approach
We will use an array dp where dp[i] represents the minimum height required to store the first i books (indices 0 through i-1). Initialize dp[0] = 0 and others as infinity.
For each book index i from 1 to n:
- Assume we start a new shelf with just this current book (
books[i-1]). The cost is at least the height of this single book plus whatever was needed for previous books (dp[i-1] + max_height_of_current_shelf). - Iterate backwards from the current book index
ito find how many preceding books can fit on the same shelf as the current one. - Maintain a running sum of widths and maximum height encountered while iterating leftwards (from
i-1down to-1). - If adding a previous book keeps us within
shelf_width, update our DP state:
dp[i] = min(dp[i], dp[j+1] + current_shelf_max_height)wherejis the index of the last added book (conceptually, if we are looking at range[k...i-1], previous cost wasdp[k]). - If adding a book exceeds width capacity, stop iterating backwards for this state because any further books to the left will only increase total width.
Complexity Analysis
- Time: . We have an outer loop running times and an inner backward loop that runs at most times (bounded by shelf capacity). Given constraints (), this is roughly operations, well within limits.
- Space: for the DP array to store intermediate results.
Solution
def minHeightShelves(books: List[List[int]], shelf_width: int) -> int:
n = len(books)
# dp[i] stores min height for first i books (indices 0..i-1)
dp = [float('inf')] * (n + 1)
# Base case: 0 books require 0 height
dp[0] = 0
for i in range(1, n + 1):
current_book_idx = i - 1
width_left = shelf_width
max_h = 0
# Iterate backwards to find the start of the last shelf ending at book[i-1]
j = current_book_idx
while j >= 0:
if books[j][0] <= width_left:
width_left -= books[j][0]
max_h = max(max_h, books[j][1])
# If we include books from index (j+1) to i-1 on this shelf,
# the previous state was after placing j+1 books.
# dp[i] is min of current best and new option:
if dp[j + 1] != float('inf'):
dp[i] = min(dp[i], dp[j + 1] + max_h)
else:
# Cannot fit this book on the shelf, stop expanding leftwards.
break
return dp[n]
Edge Cases Handled
- Single Book: The loop runs once for
i=1, inner loop checks if it fits (guaranteed by constraints), sets height to its own max height. Correct. - All Books Fit on One Shelf: Inner loop iterates all books backwards, width sum stays within limit, final DP state reflects just the maximum book height of that single shelf plus 0 previous cost. Correct.
- Forced New Shelves: If a specific book is thick or tall enough to force a break in inner loop logic (width exceeded),
dp[i]correctly falls back on splitting at earlier points via minimization.