diff options
Diffstat (limited to 'filling_bookcase_shelves.c')
-rw-r--r-- | filling_bookcase_shelves.c | 45 |
1 files changed, 45 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 +} |