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

Core interview problems are free with a full runner and lessons; Pro opens the complete library.

More Dynamic Programming problems