1105. Filling Bookcase Shelves

leetcode

Submission

2024-07-31 Filling Bookcase Shelves - Submission Detail - LeetCode

Problem:

The problem is to fill a bookcase with books, each with a given width and height, such that the total height of the shelves is minimized. We are given a list `books` where `books[i] = [width_i, height_i]` represents the width and height of the i-th book. The books must be placed in the order given. The width of each shelf is fixed and given by an integer `shelf_width`. Books can be placed on multiple shelves, but their relative ordering must stay the same.

The task is to design an algorithm that minimizes the total height of the bookcase by optimally placing books on the shelves.

Example Test Case:

Example 1: Input: `books = [[1, 3], [2, 4], [2, 2]]`, `shelf_width = 4` Output: `6` Explanation:
- Place [1, 3] and [2, 2] on the first shelf, height = 3.
- Place [2, 4] on the second shelf, height = 4.
- Total height = 3 + 4 = 7.

Solution Description:

To implement the solution optimally, we need to use dynamic programming. We will create a DP array where dp[i] represents the minimum possible height to arrange the first i books. For each book, we will iterate backward to check the possibility of placing the book on the current shelf or moving it to a new shelf. By doing this, we ensure we are considering all possible configurations and thus finding the minimal height configuration.

Time Complexity: O(n * n) due to nested iteration.
Space Complexity: O(n) for storing the DP array.

Example:

Consider `books = [[1, 3], [2, 4], [2, 2]]` and `shelf_width = 4`.

We start from the first book: [1,3]. The height is 3.
Move to the second book [2, 4]. At this point, putting it with the first creates shelf height 4 but exceeds width.
We then calculate optimal config by shifting to the next shelf if needed, checking minimum height each step.

Code Implementation

Below is the framework of the solution:

/**
 * Main function to solve the problem.
 * @param {number[][]} books - Array of books with width and height.
 * @param {number} shelfWidth - Width of each shelf.
 * @returns {number} - Minimum height of the bookcase shelves.
 */
function minHeightShelves(books, shelfWidth) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    const n = books.length;
    const dp = new Array(n + 1).fill(Infinity);
    const width = 0;
    const height = 1;
    dp[0] = 0; // No books, no height needed

    log(`books=${JSON.stringify(books)}; shelfWidth=${shelfWidth}`);
    log(`dp00=${JSON.stringify(dp)}`);
    for (let i = 1; i <= n; i++) {
        let totalWidth = 0;
        let maxHeight = 0;
        for (let j = i; j > 0; j--) {
            totalWidth += books[j - 1][width];
            if (totalWidth > shelfWidth) break;
            maxHeight = Math.max(maxHeight, books[j - 1][height]);
            dp[i] = Math.min(dp[i], dp[j - 1] + maxHeight);
        }
    }

    log(`dp01=${JSON.stringify(dp)}`);

    return dp[n];
}

// Test cases
const testCases = [
    { books: [[1, 3], [2, 4], [2, 2]], shelfWidth: 4, expected: 6 },
    { books: [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth: 4, expected: 6 },
    { books: [[1,3],[2,4],[3,2]], shelfWidth: 6, expected: 4 },
    { books: [], shelfWidth: 4, expected: 0 },
];

testCases.forEach((test, index) => {
    const result = minHeightShelves(test.books, test.shelfWidth);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});