• Posts

Problem 1105 Filling Bookcase Shelves

Problem Statement

Link - Problem 1105

Question

You are given an array books where books[i] = [thicknessi, heighti] indicates the thickness and height of the ith 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.

Note that at each step of the above process, the order of the books we place is the same order as the given sequence of books.

• For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.

Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Example 1:

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
Output: 6
Explanation:
The sum of the heights of the 3 shelves is 1 + 3 + 2 = 6.
Notice that book number 2 does not have to be on the first shelf.

Example 2:

Input: books = [[1,3],[2,4],[3,2]], shelfWidth = 6
Output: 4

Constraints:

• 1 <= books.length <= 1000
• 1 <= thicknessi <= shelfWidth <= 1000
• 1 <= heighti <= 1000

Solution

class Solution {
public:
    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
        vector<int> dp(books.size()+1,0);
        dp[0] = 0;
        dp[1] = books[0][1];
        // dp[i] represents the height of the bookshelf when ith book is placed
        for(int i = 1;i<=books.size();i++){
            int remWidth = shelfWidth-books[i-1][0];
            int height = books[i-1][1];

            dp[i] = dp[i-1]+height; // place book in new shelf

            // now check if we can move the books from previous shelf in order to reduce the value of dp[i]
            int j = i-1;
            while(j>0 && remWidth-books[j-1][0]>=0){
                remWidth -= books[j-1][0];
                height = max(height,books[j-1][1]);
                dp[i] = min(dp[i],dp[j-1]+height);
                j--;
            }
        }
        return dp[books.size()];

    }
};

Complexity Analysis

| Algorithm           | Time Complexity | Space Complexity |
| ------------------- | --------------- | ---------------- |
| Dynamic Programming | O(n^2)          | O(n)             |

Explanation

Intial Thoughts

The problem requires finding the minimum height of a bookshelf after placing all the books. We should start by understanding the constraints and how the books can be arranged on the shelves. The key is to determine when to start a new shelf and how to optimize the height of the bookshelf. We can approach this by considering the thickness and height of each book and the available shelf width. Breaking down the problem into smaller sub-problems can help in identifying a pattern or a suitable algorithm. We should also think about how to utilize dynamic programming to solve this problem efficiently.

Intuitive Analysis

To intuitively solve this problem, we can think of it as a process of placing books on shelves one by one. At each step, we have two options: place the current book on the existing shelf if there’s enough space, or start a new shelf. The decision should be based on minimizing the total height of the bookshelf. We can use a bottom-up dynamic programming approach to explore all possible arrangements and keep track of the minimum height achieved so far. The idea is to maintain a running minimum height as we place each book, considering all possible combinations of books on the current shelf and the remaining books. By comparing the minimum heights obtained from different arrangements, we can determine the optimal solution.

1. Intuition

• The problem can be approached using dynamic programming, where we build up a solution by considering each book one by one.
• We need to consider two main options for each book: placing it on a new shelf or adding it to the current shelf if there’s enough space.
• The key insight is to realize that we can use a dynamic programming table dp where dp[i] represents the minimum height of the bookshelf after placing the first i books.
• We initialize dp[0] to 0, since there are no books, and dp[1] to the height of the first book, since we have to place it on a shelf.
• For each subsequent book, we consider the two options and choose the one that results in the minimum height.
• We use a while loop to check if we can move books from the previous shelf to the current one, which allows us to potentially reduce the height of the bookshelf.
• The final result is stored in dp[books.size()], which represents the minimum height of the bookshelf after placing all books.

2. Implementation

• We start by initializing the dp table with dp[0] = 0 and dp[1] = books[0][1], which represents the base cases.
• We then iterate over the books, starting from the second book, and for each book, we calculate the remaining width remWidth and the height height of the current book.
• We update dp[i] with the minimum height between placing the book on a new shelf (dp[i-1] + height) and adding it to the current shelf if possible.
• We use a while loop to check if we can move books from the previous shelf to the current one, and update dp[i] accordingly.
• The while loop condition remWidth - books[j-1][0] >= 0 ensures that we don’t exceed the shelf width.
• We use dp[j-1] + height to calculate the new height if we move books from the previous shelf to the current one.
• Finally, we return dp[books.size()], which represents the minimum height of the bookshelf after placing all books.

Complexity Analysis

Time Complexity:

• The code has two nested loops, one iterating over each book (for(int i = 1;i<=books.size();i++)) and another iterating backwards from the current book (while(j>0 && remWidth-books[j-1][0]>=0)), resulting in a time complexity of O(n^2) due to the nested iterative structure.
• The dominant operation is the while loop inside the for loop, which can potentially run up to n times for each iteration of the outer loop, hence the quadratic time complexity.
• The Big O classification of O(n^2) is justified because the algorithm’s running time grows quadratically with the size of the input (number of books), making it less efficient for large inputs.

Space Complexity:

• The algorithm uses a dynamic programming approach, storing the minimum height of the bookshelf for each subproblem in the dp vector, which requires O(n) space where n is the number of books.
• The dp vector is the primary data structure contributing to the space complexity, as it needs to store the minimum height for each subproblem, resulting in a linear space complexity.
• The space complexity is O(n) because the algorithm only needs to store the minimum height for each subproblem, and the size of the dp vector grows linearly with the number of books.

Footnote

This question is rated as Medium difficulty.

Hints

Use dynamic programming: dp(i) will be the answer to the problem for books[i:].