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

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.