Allocate Minimum Number of Pages

Problem Statement

Given pages in books (in order) and students students, allocate contiguous books so each student reads a block and the maximum pages any student reads is minimised. Return that minimum. If students > books, return -1.

Example

Input:  books = [12,34,67,90], students = 2
Output: 113
Explanation: [12,34,67] and [90] -> max 113.

Approach

Binary search the answer in [max(books), sum(books)]. For a candidate limit, greedily count how many students are needed so no one exceeds it; needed <= students means feasible. Minimise toward the smallest feasible limit. (Same template as Split Array Largest Sum.)

Complexity

• Time: O(n log(sum - max))
• Space: O(1)

Solution Code

Python

def allocate_pages(books, students):
    if students > len(books):
        return -1
    def can(limit):
        count, cur = 1, 0
        for p in books:
            if cur + p > limit:
                count += 1
                cur = 0
            cur += p
        return count <= students
    lo, hi = max(books), sum(books)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

boolean can(int[] books, int students, int limit) {
    int count = 1, cur = 0;
    for (int p : books) {
        if (cur + p > limit) { count++; cur = 0; }
        cur += p;
    }
    return count <= students;
}
int allocatePages(int[] books, int students) {
    if (students > books.length) return -1;
    int lo = 0, hi = 0;
    for (int p : books) { lo = Math.max(lo, p); hi += p; }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (can(books, students, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

C++

bool can(vector<int>& books, int students, int limit) {
    int count = 1, cur = 0;
    for (int p : books) {
        if (cur + p > limit) { count++; cur = 0; }
        cur += p;
    }
    return count <= students;
}
int allocatePages(vector<int>& books, int students) {
    if (students > (int)books.size()) return -1;
    int lo = 0, hi = 0;
    for (int p : books) { lo = max(lo, p); hi += p; }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (can(books, students, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Key Takeaways

• Return -1 when there are more students than books.
• This is the Split Array Largest Sum pattern in disguise.
• Reference: classic Book Allocation problem (GeeksforGeeks).