Filling Bookcase Shelves Solution in Java

Ah, the age-old dilemma of fitting books on a shelf without making it look like a tornado hit a library. You know the struggle: you buy a new book, and suddenly your meticulously organized shelf looks like a game of Tetris gone wrong. Welcome to the world of Filling Bookcase Shelves, where we tackle the challenge of stacking books in a way that minimizes the height of the shelves while adhering to a strict width limit.

Imagine you have a shelf that can only hold so much width, and you have a collection of books of varying thicknesses and heights. The goal? To stack them in a way that keeps your shelf from looking like a Leaning Tower of Pisa.

Problem Description

Given an array of books, where each book is represented by its thickness and height, and a shelf width, the task is to determine the minimum height of the shelves needed to accommodate all the books.

Solution Links

Code Solution


class Solution {
  public int minHeightShelves(int[][] books, int shelfWidth) {
    final int n = books.length;
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int i = 0; i < books.length; ++i) {
      int sumThickness = 0;
      int maxHeight = 0;
      for (int j = i; j >= 0; --j) {
        final int thickness = books[j][0];
        final int height = books[j][1];
        sumThickness += thickness;
        if (sumThickness > shelfWidth)
          break;
        maxHeight = Math.max(maxHeight, height);
        dp[i + 1] = Math.min(dp[i + 1], dp[j] + maxHeight);
      }
    }

    return dp[n];
  }
}

Approach Explanation

The approach used in the code 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 given width. We keep track of the total thickness and the maximum height of the books on that shelf. If adding another book exceeds the shelf width, we stop and calculate the minimum height needed.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²)
Space Complexity	O(n)

Real-World Example

Picture this: you just bought a new series of books, and your shelf is already packed with your favorite novels. You need to fit these new books in without making your shelf look like a chaotic mess. By applying the solution to the Filling Bookcase Shelves problem, you can efficiently stack your books, ensuring that your shelf remains neat and tidy, while also maximizing the use of space.