Book Allocation Problem

Problem Statement

Given an array of integers books[] where books[i] represents the number of pages in the i-th book, and an integer m representing the number of students, allocate books to students such that:

1. Each student gets at least one book
2. Each book is allocated to exactly one student
3. Books are allocated in contiguous order
4. The maximum number of pages allocated to any student is minimized

Return the minimum possible value of the maximum pages allocated.

Constraints:

• 1 ≤ n ≤ 10^5
• 1 ≤ books[i] ≤ 10^6
• 1 ≤ m ≤ n

Example:

• Input: books = [12, 34, 67, 90], m = 2
• Output: 113
• Explanation: Allocation: [12, 34, 67] and [90] → max = 113. Or [12] and [34, 67, 90] → max = 191. Optimal is 113.

Example 2:

• Input: books = [10, 20, 30, 40], m = 2
• Output: 60
• Explanation: [10, 20, 30] = 60 and [40] = 40. Maximum = 60

Approach 1: Brute Force (Recursion)

Intuition

Try all possible ways to partition the array into m contiguous parts and find the partition that minimizes the maximum sum among all parts.

Algorithm

1. Use recursion to try all possible partitions
2. For each partition, calculate the maximum sum
3. Track the minimum of all maximum sums
4. Base case: if only one student left, give all remaining books

import java.util.*;

public class Solution {
    private int minPages = Integer.MAX_VALUE;
    
    private void solve(int[] books, int idx, int m, int currentMax) {
        int n = books.length;
        
        // Base case: last student gets remaining books
        if (m == 1) {
            int sum = 0;
            for (int i = idx; i < n; i++) {
                sum += books[i];
            }
            minPages = Math.min(minPages, Math.max(currentMax, sum));
            return;
        }
        
        int sum = 0;
        for (int i = idx; i <= n - m; i++) {
            sum += books[i];
            solve(books, i + 1, m - 1, Math.max(currentMax, sum));
        }
    }
    
    public int allocateBooks(int[] books, int m) {
        if (m > books.length) return -1;
        
        minPages = Integer.MAX_VALUE;
        solve(books, 0, m, 0);
        return minPages;
    }
}

Complexity Analysis

• Time Complexity: O(n^n) - Exponential due to trying all possible partitions
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Binary Search on Answer (Optimal)

Intuition

The key insight is that if we can allocate books such that no student gets more than X pages, we can also allocate with any limit > X. This monotonic property allows binary search on the answer.

Key Observations:

1. Minimum possible answer = max(books[i]) (single largest book)
2. Maximum possible answer = sum(books[i]) (all books to one student)
3. For a given limit, greedily check if allocation is possible
4. Binary search between min and max to find optimal answer

Algorithm

1. Set low = max(books), high = sum(books)
2. Binary search on the maximum pages limit
3. For each mid, check if we can allocate with at most mid pages per student
4. If possible, try smaller limit; otherwise, increase limit

import java.util.*;

public class BookAllocation {
    private boolean canAllocate(int[] books, int m, int maxPages) {
        int students = 1;
        int currentSum = 0;
        
        for (int pages : books) {
            // Single book exceeds limit
            if (pages > maxPages) return false;
            
            if (currentSum + pages > maxPages) {
                // Allocate to next student
                students++;
                currentSum = pages;
                
                if (students > m) return false;
            } else {
                currentSum += pages;
            }
        }
        
        return true;
    }
    
    public int allocateBooks(int[] books, int m) {
        int n = books.length;
        if (m > n) return -1;
        
        int low = 0, high = 0;
        for (int pages : books) {
            low = Math.max(low, pages);
            high += pages;
        }
        
        int result = high;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (canAllocate(books, m, mid)) {
                result = mid;
                high = mid - 1;  // Try smaller limit
            } else {
                low = mid + 1;   // Need larger limit
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        BookAllocation ba = new BookAllocation();
        int[] books = {12, 34, 67, 90};
        System.out.println(ba.allocateBooks(books, 2));  // Output: 113
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log(sum - max))
  • Binary search runs O(log(sum - max)) times
  • Each canAllocate check takes O(n)
• Space Complexity: O(1) - Only using variables

Variant: Return the Actual Allocation

Key Takeaways

1. Binary Search on Answer: When minimizing maximum (or maximizing minimum), binary search on the answer space
2. Monotonic Property: If limit X works, all limits > X also work
3. Greedy Verification: Use greedy approach to check if a limit is feasible
4. Search Space Bounds: min = max(individual), max = sum(all)
5. Edge Cases: Handle m > n (impossible allocation)
6. Similar Problems: Painter's Partition, Split Array Largest Sum, Capacity to Ship Packages
7. Pattern Recognition: "Minimize maximum" or "Maximize minimum" often indicates binary search on answer