Given an array pages[] of book page counts and m students, allocate books to students such that: (1) each student gets a contiguous subset of books, (2) each book is allocated to exactly one student. Minimize the maximum pages allocated to any student.
pages = [12,34,67,90], m = 2113pages = [10,20,30,40], m = 260pages = [15,17,20], m = 232lo = max(pages), hi = sum(pages), ans = hilo ≤ hi: compute mid = lo + (hi−lo)/2midans=mid, hi=mid−1 (try smaller)lo=mid+1 (limit too tight)ans — minimum possible maximum pagesThe feasibility function is monotone: if we can allocate with max limit X, we can also do it with any larger limit. So there is a threshold — everything below it is infeasible, everything above is feasible. Binary search finds the minimum feasible value in O(log(sum)) iterations, each costing O(n) for greedy simulation.
Trying every way to split the books is exponential. But if a page limit works, every bigger limit works too.
Binary search the page limit between the largest book and the total. For a limit, give books to a student until the next one would exceed it, then move to the next student. If the students needed are at most the given number, try smaller.
This is the same problem as split array largest sum. Binary search the limit, and count students greedily.
Run the animation above on your own input, or watch the 1:25 video explanation of Allocate Minimum Number of Pages with a dry run and Java code.