Allocate minimum number of pages to each student

Question

Please can anyone give the proper algorithm to solve this question. Not the code just algorithm. Thank you.

You are given N number of books. Every ith book has Pi number of pages. You have to allocate books to M number of students so that maximum number of pages alloted to a student is minimum. A book will be allocated to exactly one student. Each student has to be allocated atleast one book.

Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order.

Here's a link to problem statement.

Answer 1

Set the maximum to X pages per student.

To check if this is feasible just start allocating books to the first student until the next book would push over the threshold X. Then switch to the next and so on (this works because they say the allocations need to be contiguous).

If you run out of books then it's feasible (you can always go back and give students less books to read to fit the other students). If you run out of students then it's not.

This check will be O(N) where N is the number of books.

Now that you have this, do a binary search for X. Complexity is O(NlogM) where N is the number of books and M is the total number of pages.