Filling Bookcase Shelves
Intuition
Solution
class Solution:
def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
combines = [] # (current_width, current_height, total_height)
width, height = books.pop(0)
combines.append((width, height, height))
for width, height in books:
tmp = []
for w, h, t in combines:
if w + width <= shelf_width:
tmp.append((w + width, max(h, height), t + max(h, height) - h))
tmp.append((width, height, min([i[2] for i in combines]) + height))
combines = tmp
return min([i[2] for i in combines])