Filling Bookcase Shelves

MediumDynamic Programming1d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You must place books on a bookcase in the given order. Book i has thickness books[i][0] and height books[i][1]. Each shelf holds a contiguous run of the remaining books whose total thickness is at most shelfWidth, and a shelf is as tall as its tallest book. Shelves are stacked, so the bookcase's total height is the sum of its shelf heights. Books must keep their original order (you fill one shelf, then start the next). Return the minimum possible total height.

Examples

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
Output: 6
Shelves `[book0]`, `[book1, book2]`, `[book3..book6]` have heights 1, 3, 2.
Input: books = [[1,3],[2,4],[3,2]], shelfWidth = 6
Output: 4
All three books fit on one shelf of height 4.

Constraints

  • `1 <= books.length <= 1000`
  • `1 <= books[i][0] <= shelfWidth <= 1000`
  • `1 <= books[i][1] <= 1000`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 1d dp problems