Filling Bookcase Shelves Solution in C++

Problem Description

Ah, the age-old dilemma of how to fit your beloved books onto a shelf without creating a leaning tower of Pisa situation. Welcome to the “Filling Bookcase Shelves” problem, where you get to play the role of a bookish architect! The challenge is to arrange a series of books on shelves, ensuring that the total width of the books on each shelf does not exceed a given limit. And let’s be honest, if you’ve ever tried to stack books, you know that the height of the shelf is just as important as the width.

Imagine you have a collection of books, each with a specific width and height. Your task is to minimize the total height of the shelves while ensuring that no shelf exceeds the specified width. It’s like trying to fit your entire library into a tiny apartment—good luck with that!

Code Solution

class Solution {
 public:
  int minHeightShelves(vector>& books, int shelfWidth) {
    // dp[i] := the minimum height to place the first i books
    vector dp(books.size() + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 0; i < books.size(); ++i) {
      int sumThickness = 0;
      int maxHeight = 0;
      // Place books[j..i] on a new shelf.
      for (int j = i; j >= 0; --j) {
        const int thickness = books[j][0];
        const int height = books[j][1];
        sumThickness += thickness;
        if (sumThickness > shelfWidth)
          break;
        maxHeight = max(maxHeight, height);
        dp[i + 1] = min(dp[i + 1], dp[j] + maxHeight);
      }
    }

    return dp.back();
  }
};

Approach

The approach used in this solution is dynamic programming. We maintain an array dp where dp[i] represents the minimum height required to place the first i books. For each book, we check how many books can fit on a new shelf without exceeding the width limit. We keep track of the total thickness and the maximum height of the books on that shelf. By iterating through the books and updating the dp array, we can find the minimum height required for all books.

Time and Space Complexity

• Time Complexity: O(n²), where n is the number of books. This is because for each book, we may need to check all previous books to see how many can fit on the shelf.
• Space Complexity: O(n), for the dp array that stores the minimum heights.

Real-World Example

Imagine you’re moving into a new apartment and you have a collection of books that you absolutely cannot part with. You have a limited shelf space, and you want to make sure that your books are not only organized but also look aesthetically pleasing. This problem is akin to that scenario—finding the optimal way to arrange your books so that they fit perfectly on your shelves without toppling over or creating a chaotic mess.