Search⌘ K
Home
Courses
Mastering Algorithms for Problem Solving in Java

Solution: Greedy Algorithms

Explore the application of a greedy algorithm to store a fixed sequence of books on shelves efficiently. Understand the step-by-step process of filling shelves to their maximum capacity under length constraints, and learn to implement the solution in Java to determine the minimum number of shelves required.

We'll cover the following...

Let's practice what we've learned so far.

Task

We’ve been hired to store a sequence of nn books on shelves in a library. The order of the books is fixed by the cataloging system and cannot be changed; each shelf must store a contiguous interval of the given sequence of books. We are given two arrays, H[1..n]H[1 .. n] and T[1..n]T[1 .. n], where H[i]H[i] and T[i]T[i] are, respectively, the height and thickness of the iith book in the sequence. All shelves in this library have the same length LL; the total thickness of all books on any single shelf cannot exceed LL. Suppose all the books have the same height ...