Book Allocation — Binary Search on Answer

What does it solve?

Given N books with page counts and M students, assign contiguous books to each student so that the maximum pages read by any student is minimised. Every student must get at least one book.

Key insight: binary search on the answer — the possible maximum page limit. For a given limit mid, a greedy check tells us if M students are enough. This turns O(N·S) brute-force into O(N log S).

The core idea

// binary search on answer
lo = max(pages), hi = sum(pages)
ans = -1
while lo <= hi:
  mid = (lo + hi) / 2
  if canAllocate(mid, M):
    ans = mid; hi = mid - 1
  else: lo = mid + 1

Complexity

Time complexity

O(N log S)

Binary search runs O(log S) times where S = sum of all pages. Each check is O(N) — a greedy linear scan.

Space complexity

O(1)

Only a handful of pointer and counter variables. No extra data structure needed.

Examples & edge cases

Live animation — binary search on the answer

lo hi mid (testing) feasible → ans updated not feasible → lo moves up

Search space — [lo … hi]

lo —

mid —

hi —

best answer —

feasible? —

Books (page counts) — testing mid = —

Greedy allocation for mid = —

lo = — hi = — mid = — ans = —

Step — of —

lo (lower bound)

—

max single book

hi (upper bound)

—

sum of all pages

mid (candidate)

—

Best answer

—

Select an example and press Play to start.

✓ Answer: —

Speed Medium

Step-by-step table

Step	Phase	lo	hi	mid	Students needed	Feasible?	Action	Best ans

C++ implementation

book_allocation.cpp

#include <bits/stdc++.h>
using namespace std;

// Check if we can allocate books to m students with max pages = limit
bool canAllocate(vector<int>& pages, int m, int limit) {
    int students = 1, curSum = 0;
    for (int p : pages) {
        if (p > limit) return false; // single book exceeds limit
        if (curSum + p > limit) {
            students++;            // start a new student
            curSum = p;
            if (students > m) return false;
        } else {
            curSum += p;
        }
    }
    return true;
}

int allocateBooks(vector<int>& pages, int m) {
    if (m > pages.size()) return -1; // impossible

    int lo = *max_element(pages.begin(), pages.end());
    int hi = accumulate(pages.begin(), pages.end(), 0);
    int ans = hi;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canAllocate(pages, m, mid)) {
            ans = mid;   // feasible — try smaller limit
            hi = mid - 1;
        } else {
            lo = mid + 1; // not feasible — need bigger limit
        }
    }
    return ans;
}

int main() {
    vector<int> pages = {12, 34, 67, 90};
    cout << allocateBooks(pages, 2) << "\n"; // 113
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars