Allocate Books (Book Allocation Problem)

Given N books with pages[], allocate books to M students such that each student gets at least one book, books are consecutive, and the maximum pages allocated to a student is minimized.

Example 1

Input: pages=[12,34,67,90], M=2 → Output: 113

Example 2

Input: pages=[10,20,30,40], M=2 → Output: 60

Solution Approach

Binary search on the answer (maximum pages). Check feasibility: can M students read all books with max <= mid?

lo=max(pages), hi=sum(pages).
For mid: greedily assign books until current student's pages exceed mid, then assign to next student.
If students needed <= M: hi=mid. Else lo=mid+1.

Java

class Solution {
    public int books(int[] pages, int m) {
        int lo = 0, hi = 0;
        for (int p : pages) { lo = Math.max(lo, p); hi += p; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canAllocate(pages, m, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    private boolean canAllocate(int[] pages, int m, int maxPages) {
        int students = 1, current = 0;
        for (int p : pages) {
            if (current + p > maxPages) { students++; current = 0; }
            current += p;
            if (students > m) return false;
        }
        return true;
    }
}

Time Complexity: O(N log(sum))
Space Complexity: O(1)