Binary Search: Allocate Books (Book Allocation)

1. Problem Statement & Overview

The Allocate Books problem is a classic, highly challenging algorithmic challenge frequently asked in technical interviews. It tests your ability to combine the Binary Search paradigm with greedy allocation logic under rigid constraints.

You are given an array representing the page counts of $N$ books, where each element $A[i]$ denotes the number of pages in the $i$-th book. You are also given an integer $M$ representing the number of students. Your objective is to distribute all the books among the $M$ students while strictly adhering to three rules:

1. At Least One Book: Each student must be allocated at least one book.
2. Single Owner: Each book can be allocated to only one student.
3. Contiguous Allocation: Book allocation must be done in a contiguous manner (e.g., if student 1 gets book 0 and book 1, they cannot also receive book 3 while skipping book 2).

The Objective Metric

Minimize the maximum number of pages assigned to any single student across all possible valid allocations. If allocation is impossible (e.g., $M > N$), return -1.

2. Real-Life Analogy: The Task Distribution Metaphor

Imagine managing a publishing house warehouse where you need to distribute incoming shipments of heavy manuscript volumes across a team of interns.

• You cannot tear pages apart or share chapters across multiple interns (single owner).
• Every intern must carry at least one manuscript to justify their shift (at least one book).
• You must hand over manuscripts in the exact sequence they arrived on the assembly belt; you cannot cherry-pick scattered books out of order (contiguous manner).
• Your goal is to find the most balanced workload distribution so that the hardest-working intern (the one carrying the maximum number of pages) bears the minimum possible burden.

3. Initial Feasibility Check (Edge Cases)

Before running any optimization or search algorithm, check whether the allocation is fundamentally possible:

• Too Few Books, Too Many Students ($M > N$): If you have 5 books and 6 students, it is physically impossible to give every student at least one book. In this scenario, immediately return -1.

4. Understanding the Brute Force Approach

Consider an array of 5 books with page counts [25, 46, 28, 49, 24] and $M = 4$ students.

Manual Configuration Walkthrough

Let's test potential upper limits for the maximum pages a student is allowed to hold:

• Trial 1 (Limit = 73):
  • Student 1: 25
  • Student 2: 46
  • Student 3: 28
  • Student 4: 49 + 24 = 73
  • Max Pages assigned: 73 (Valid for 4 students)
• Trial 2 (Limit = 71):
  • Student 1: 25 + 46 = 71
  • Student 2: 28
  • Student 3: 49
  • Student 4: 24
  • Max Pages assigned: 71 (Valid for 4 students)

By testing sequentially from the smallest possible barrier up to the sum of all pages, we can find the minimum valid maximum. However, linear search is inefficient ($O(\text{Sum} - \text{Max}) \times N$). We need a faster strategy.

5. Establishing the Search Space Range

To apply Binary Search, we must determine the exact boundaries (low and high) of our answer range:

• Lower Bound (low): What is the absolute minimum possible value for the maximum pages a student can hold?
  • Answer: It must be at least equal to the maximum single book size in the array. If the largest book has 49 pages, a student must be allowed to hold at least 49 pages; otherwise, they cannot even take that single book. Thus, low = *max_element(A.begin(), A.end()).
• Upper Bound (high): What is the absolute maximum possible value?
  • Answer: If $M = 1$, a single student must take all the books. Thus, high = sum(A).

Our search space for the optimal answer always lies strictly between:

6. The Helper Function: Counting Required Students

Given a maximum allowed page limit (mid), we need a greedy helper function to calculate how many students are required to distribute all books without exceeding that limit.

Algorithm for countStudents(A, maxPages)

1. Initialize students = 1 and currentPages = 0.
2. Iterate through each book in the array:
   • If currentPages + book <= maxPages, add the book to the current student's workload.
   • Else, the current student cannot take this book without exceeding the limit. Increment students++, and assign the current book to the new student (currentPages = book).
3. Return the total students required.

int countStudents(vector<int>& arr, int maxPages) {
    int students = 1;
    long long currentPages = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (currentPages + arr[i] <= maxPages) {
            currentPages += arr[i];
        } else {
            students++;
            currentPages = arr[i];
        }
    }
    return students;
}

7. Step-by-Step Binary Search Evolution

As the page limit (mid) increases, the number of students required to distribute the books decreases (fewer students are needed because each student can carry a heavier load). Conversely, a smaller page limit requires more students. This monotonic property allows us to apply Binary Search.

Binary Search Workflow

8. Complete C++ Implementation

Here is the complete, production-grade implementation combining the constraints, helper function, and binary search logic:

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

class Solution {
private:
    // Helper function to count how many students are needed for a given max page limit
    int countStudents(vector<int>& arr, int maxPages) {
        int students = 1;
        long long currentPages = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (currentPages + arr[i] <= maxPages) {
                currentPages += arr[i];
            } else {
                students++;
                currentPages = arr[i];
            }
        }
        return students;
    }

public:
    int allocateBooks(vector<int>& arr, int n, int m) {
        // Edge case: More students than books
        if (m > n) return -1;

        int low = *max_element(arr.begin(), arr.end());
        int high = accumulate(arr.begin(), arr.end(), 0);
        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int studentsReq = countStudents(arr, mid);

            if (studentsReq > m) {
                // If students required exceed M, our limit 'mid' is too small.
                // We must increase the allowed maximum pages.
                low = mid + 1;
            } else {
                // Valid allocation possible. Try to find a smaller maximum on the left.
                ans = mid;
                high = mid - 1;
            }
        }
        return ans;
    }
};

9. Complexity Analysis

10. Summary and Key Takeaways

• Problem Classification: An advanced optimization problem solvable via Binary Search on Answers (Min of Max pattern).
• Initial Validation: Always check if $M > N$ to instantly handle impossible allocations and return -1.
• Search Space Bounds:
  • low is always set to the maximum element in the book array (every student needs capacity for at least the largest book).
  • high is always set to the sum of all elements (the worst-case scenario where one student takes all books).
• Monotonicity: As the allowed page limit increases, the required number of student counts strictly decreases, making Binary Search applicable.
• Greedy Verification: The helper function assigns books contiguously up to the current threshold (mid), incrementing the student count whenever the threshold is breached.
• Optimal Efficiency: Reducing the linear search range to a logarithmic binary search drops the time complexity from $O(\text{Sum} \times N)$ down to $O(N \log(\text{Sum}))$.