Medium · Dynamic Programming

Filling Bookcase Shelves

Given books[i] = [thicknessᵢ, heightᵢ] and an integer shelfWidth, place the books on shelves in their given order, each shelf holding books of total thickness at most shelfWidth and standing as tall as its tallest book; return the minimum possible total height of the bookcase.

Examples

Example 1

{
  "books": [
    [1, 1],
    [2, 3],
    [2, 3],
    [1, 1],
    [1, 1],
    [1, 1],
    [1, 2]
  ],
  "shelfWidth": 4
}

Output: height 6

Example 2

{
  "books": [
    [1, 3],
    [2, 4],
    [3, 2]
  ],
  "shelfWidth": 4
}

Output: height 6

Rebuild it in the studio

Open every published interview problem, solution, scene, and memory room free, with no account.