This problem is about fairly distributing work (in the form of book pages) among a group (students), such that no single person is overloaded compared to others.
The key constraint is that each student must receive a contiguous block of books. You cannot give a student book 1 and book 3 while skipping book 2.
Let's explore different scenarios to understand what the correct answer should look like:
- Case 1: More students than books — This is not possible. Every student must get at least one book, and if books are fewer than students, we return
-1
.
- Case 2: Equal number of students and books — This means each student will get exactly one book. The answer will be the maximum number of pages among the books because that’s the worst-case individual load.
- Case 3: Only one student — The only student must read all the books. So the answer will be the total number of pages of all books.
- Case 4: Normal case (fewer students than books) — This is where optimization is needed. We try different ways to divide books into blocks such that the student with the highest load has to read the least possible number of pages. This is done by exploring different values for the "maximum pages" and checking if the books can be divided accordingly.
- Case 5: Empty book list — There's nothing to allocate, so we return
-1
.
- Case 6: Zero students — No one is there to read the books. This is invalid input, so return
-1
.
The solution uses a smart way to search the answer using Binary Search instead of trying all combinations. It searches between the range max(arr)
(because no student can be assigned fewer pages than the largest book) and sum(arr)
(the case where one student gets everything). For each mid-value in this range, we check: is it possible to allocate books so that no student gets more than mid
pages? If yes, we try to find a smaller answer. If not, we look for a higher value.
This process gives us the minimum possible value for the maximum pages a student has to read in a fair allocation.