diff options
-rw-r--r-- | filling_bookcase_shelves.c | 45 | ||||
-rw-r--r-- | filling_bookcase_shelves.py | 43 |
2 files changed, 88 insertions, 0 deletions
diff --git a/filling_bookcase_shelves.c b/filling_bookcase_shelves.c new file mode 100644 index 0000000..3a05d2b --- /dev/null +++ b/filling_bookcase_shelves.c @@ -0,0 +1,45 @@ +// 1105. Filling Bookcase Shelves +#include "leetcode.h" + +/* + * you are given an array 'books' where 'books[i] = [thinkness, height]' + * indicates the thickness and height of the i'th book. you are also given an + * integer 'shelfWidth'. we want to place these books in order onto bookcase + * shelves that have a total width 'shelfWidth'. we chose some of the books to + * place on this shelf such that the sum of their thickness is less than or + * equal to 'shelfWidth' then build another level of the shelf of the bookcase + * so that the total height of the bookcase has increased by the maximum height + * of the books we just put down. we repeat this process until there are no more + * books to place. + */ + +int minHeightShelves(int **books, int booksSize, int *booksColSize, + int shelfWidth) { + int *dp = (int *)malloc((booksSize + 1) * sizeof(int)); + dp[0] = 0; + for (int i = 1; i <= booksSize; i++) { + int min = dp[i - 1] + books[i - 1][1]; + int height = books[i - 1][1]; + int width = books[i - 1][0]; + int j = i - 2; + while (j >= 0 && width + books[j][0] <= shelfWidth) { + width += books[j][0]; + height = (height > books[j][1]) ? height : books[j][1]; + min = (min < height + dp[j]) ? min : height + dp[j]; + --j; + } + dp[i] = min; + } + int ans = dp[booksSize]; + free(dp); + return ans; +} + +int main() { + int b1[7][2] = {{1, 1}, {2, 3}, {2, 3}, {1, 1}, {1, 1}, {1, 1}, {1, 2}}, + b2[3][2] = {{1, 3}, {2, 4}, {3, 2}}, bcs1 = 7, bcs2 = 3; + printf("%d\n", + minHeightShelves((int **)b1, ARRAY_SIZE(b1), &bcs1, 4)); // expect: 6 + printf("%d\n", + minHeightShelves((int **)b2, ARRAY_SIZE(b2), &bcs2, 6)); // expect: 4 +} diff --git a/filling_bookcase_shelves.py b/filling_bookcase_shelves.py new file mode 100644 index 0000000..d66deba --- /dev/null +++ b/filling_bookcase_shelves.py @@ -0,0 +1,43 @@ +# 1105. Filling Bookcase Shelves + +""" +you are given an array 'books' where 'books[i] = [thinkness, height]' +indicates the thickness and height of the i'th book. you are also given an +integer 'shelfWidth'. we want to place these books in order onto bookcase +shelves that have a total width 'shelfWidth'. we chose some of the books to +place on this shelf such that the sum of their thickness is less than or +equal to 'shelfWidth' then build another level of the shelf of the bookcase +so that the total height of the bookcase has increased by the maximum height +of the books we just put down. we repeat this process until there are no more +books to place. +""" + + +class Solution(object): + def minHeightShelves(self, books, shelfWidth): + """ + :type books: List[List[int]] + :type shelfWidth: int + :rtype: int + """ + n = len(books) + dp = [float("inf") for _ in range(n + 1)] + dp[0] = 0 + for i in range(1, n + 1): + width, height, j = shelfWidth, 0, i - 1 + while j >= 0 and width - books[j][0] >= 0: + width -= books[j][0] + height = max(height, books[j][1]) + dp[i] = min(dp[i], dp[j] + height) + j -= 1 + return dp[n] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.minHeightShelves( + books=[[1, 1], [2, 3], [2, 3], [1, 1], [1, 1], [1, 1], [1, 2]], shelfWidth=4 + ) + ) + print(obj.minHeightShelves(books=[[1, 3], [2, 4], [3, 2]], shelfWidth=6)) |