Allocate Minimum Pages
Split an array of book page-counts among k students, contiguous books each, minimizing the maximum pages any student reads.
Intuition
Flip the question: 'can we split so nobody exceeds cap X?' is easy to check greedily, and it's monotone in X. Binary search the smallest workable cap. This min-max-split pattern also solves Split Array Largest Sum and Capacity to Ship Packages.
The mirror of aggressive cows: minimise the maximum load. Guess a page limit, greedily fill students until one overflows, and count how many you needed — fewer students needed means the limit was generous. The search bounds encode the extremes: no student can carry less than the biggest single book, and one student could carry them all.
Approach
The feasibility check
Sweep books, packing greedily; open a new student when the current one would exceed the cap. Feasible iff students used ≤ k.
Monotone → binary search
A bigger cap never needs more students. Search caps between max(book) and sum(books).
Converge on the minimum
Feasible → try smaller (hi = mid); infeasible → need bigger (lo = mid+1). lo ends at the optimum.
Solution & live demo
Common pitfalls
Starting the search at zero or one
lo, hi = 1, sum(books)
lo, hi = max(books), sum(books)
A limit below the largest single book is infeasible — that book fits nowhere, and the greedy check would loop or miscount. The largest book is a hard floor on any valid answer.
Missing the impossible case
def allocate_pages(books, k):
lo, hi = max(books), sum(books)if k > len(books): return -1
With more students than books, someone must get zero books, which the problem forbids — the expected answer is -1. The binary search itself would happily return a number.
Inverting the feasibility comparison
if students_needed(mid) <= k: lo = mid + 1 else: hi = mid
if students_needed(mid) <= k: hi = mid else: lo = mid + 1
Needing at most k students means the limit is workable, and since we're minimising, a workable limit becomes the new upper bound. Pushing lo up instead walks away from the answer and returns the largest infeasible value.
Edge cases
Classic GFG version returns −1; every student needs a book.
Only the full sum works — the search converges to it.