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

Solution: Greedy Algorithms

Explore how to apply greedy algorithms to arrange books on shelves efficiently when the order cannot be changed. Understand the algorithm that fills shelves to capacity before moving on, ensuring minimal shelves are used. This lesson guides you through analyzing the approach and implementing it in Python, enhancing your problem-solving with greedy strategies.

We'll cover the following...

Let's practice what we have 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. You 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 hh ...