Optimal way to read a book having N chapters in M days

Question

I came across this interview question: Given a book with N chapters (each chapter has of course different number of pages), what is the optimal way to complete the entire book in M days with the constraint that a chapter has to be read completely on the same day.

Example:

Chapters[] = {7, 5, 3, 9, 10}
Days = 4

One should read:

Chapter1 on Day1, Chapters2 and Chapter3 on Day2, Chapter4 on Day3 and Chapter5 on Day4.

I understand that the idea should be to minimize the sum of absolute differences of total pages read with the average number of pages that one should 'ideally' read on one day. However, I am not able to translate this idea to a data structure and an algorithm. Any other idea or inputs are appreciated.

Answer 1

You can use dynamic programming.

1. The average is equal to totalNumberOfPages / numberOfDays and it does not depend on the way we read the book.

2. The state is (number of chapters we have finished, the number of days we have already spent). The value of a state is the minimum sum of absolute differences so far.

3. The base case if f(0, 0) = 0.

4. Transitions are as follows:

   • Let's assume that the current state is (chapters, days).

   • We can iterate over the number of chapters we will read the next day(I will call it add) and make the following transition: f(chapters + add, days + 1) = min(f(chapters + add, days + 1), f(chapters, days) + abs(average - the number of pages in chapter + 1 ... chapter + add chapters).

5. The answer is f(totalNumberOfChapters, totalNumberOfDays).

This solution is based on an assumption that our goal is to "minimize the sum of absolute differences of total pages read with the average number of pages that one should 'ideally' read on one day".

But if the problem statement does not say what the criterion of optimality is, I would suggest minimizing the maximum number of pages read during one day(in my opinion, the goal not too read to much in a row makes more sense). In this case, there is a more simple and efficient solution: we can binary search over the answer and use a greedy algorithm to check if a fixed candidate is feasible.