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])