GeeksforGeeks Medium

Allocate Minimum Pages

Split an array of book page-counts among k students, contiguous books each, minimizing the maximum pages any student reads.

binary-searchgreedy

Open on GeeksforGeeks ↗

02

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.

03

Approach

1

The feasibility check

Sweep books, packing greedily; open a new student when the current one would exceed the cap. Feasible iff students used ≤ k.

2

Monotone → binary search

A bigger cap never needs more students. Search caps between max(book) and sum(books).

3

Converge on the minimum

Feasible → try smaller (hi = mid); infeasible → need bigger (lo = mid+1). lo ends at the optimum.

04

Solution & live demo

python

▶1def allocate_pages(books, k):
▶2    if k > len(books): return -1
▶3    def students_needed(cap):
▶4        cnt, cur = 1, 0
▶5        for b in books:
▶6            if cur + b > cap:
▶7                cnt += 1; cur = 0
▶8            cur += b
▶9        return cnt
▶10    lo, hi = max(books), sum(books)
▶11    while lo < hi:
▶12        mid = (lo + hi) // 2
▶13        if students_needed(mid) <= k: hi = mid
▶14        else: lo = mid + 1
▶15    return lo

05

Edge cases

k > number of books

Classic GFG version returns −1; every student needs a book.

k = 1

Only the full sum works — the search converges to it.

06

Complexity

Time

O(n log S)

Space

O(1)

S = sum − max; each guess is one greedy sweep.