We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Filling Bookcase Shelves

Number: 1196

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given a sequence of books where each book is represented as [thickness, height], we need to place them on shelves. Each shelf can hold consecutive books (in order) as long as the sum of their thickness does not exceed a given shelfWidth. The height of a shelf equals the maximum height of the books on that shelf. The goal is to partition the books into shelves such that the total height of the bookcase is minimized.

Key Insights

  • This is an optimization problem where we need to decide breakpoints for shelves while preserving the order of books.
  • Dynamic Programming (DP) is suitable because the optimal solution for the first i books can be built from solutions for fewer books.
  • For each book i, we can try to form a shelf ending at i by looking backwards and maintaining the cumulative thickness and maximum height.
  • The state transition becomes: dp[i] = min(dp[j] + currentShelfHeight) where the sum of thickness from book j to i stays within shelfWidth.

Space and Time Complexity

Time Complexity: O(n^2), where n is the number of books. In worst-case scenarios, we check all partitions ending at each book. Space Complexity: O(n) for the DP array.

Solution

We use a dynamic programming approach. We define dp[i] as the minimum total height for arranging the first i books. For every book i (1-indexed in our DP formulation), we iterate backwards to determine which previous books can be grouped on the same shelf. We accumulate the sum of thickness and track the maximum height within the current potential shelf. If the accumulated thickness exceeds shelfWidth, we stop considering more books. The state transition updates dp[i] by taking the minimum between its current value and dp[j] plus the current shelf height for books from j+1 to i.

Data Structures / Algorithms Used:

  • Array for storing dp states,
  • Iteration with nested loops to check all possible partitions efficiently.

This approach thoroughly explores all valid placements for shelves while ensuring the order of books is maintained. Special care is taken to update the current shelf height as we iterate backwards from each book.

Code Solutions

# Dynamic Programming Solution in Python

def minHeightShelves(books, shelfWidth):
    # Number of books.
    n = len(books)
    # dp[i] will hold the minimum height for placing first i books.
    dp = [float('inf')] * (n + 1)
    # Base Case: no books, no height.
    dp[0] = 0
    
    # Iterate over each book index from 1 to n.
    for i in range(1, n + 1):
        width = 0  # Current shelf width used.
        maxHeight = 0  # Maximum height on the current shelf.
        # Try placing books from i-1 backwards on this shelf.
        for j in range(i - 1, -1, -1):
            width += books[j][0]  # Add thickness of the j-th book.
            if width > shelfWidth:
                break  # Cannot add more books on this shelf.
            # Update the maximum height encountered in this potential shelf.
            maxHeight = max(maxHeight, books[j][1])
            # Update dp[i] with the minimal height option.
            dp[i] = min(dp[i], dp[j] + maxHeight)
            
    return dp[n]

# Example usage:
books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]
shelfWidth = 4
print(minHeightShelves(books, shelfWidth))  # Expected output: 6
← Back to All Questions