Allocate Minimum Pages (Book Allocation)

Given an array of integers pages representing the number of pages in N different books, and an integer M representing the number of students. The books are arranged in ascending order of the number of pages.

The task is to assign books to students such that:

1. Each book is assigned to exactly one student.
2. Each student is assigned at least one book.
3. The books are assigned in a contiguous sequence.
4. The maximum number of pages assigned to any student is minimized.

Examples

Example

• Pages: [12, 34, 67, 90]
• Students (M): 2
• Output: 113
• Explanation: There are 2 students. The books can be distributed in the following ways:
  1. Student 1: [12], Student 2: [34, 67, 90] -> Max pages = 34 + 67 + 90 = 191
  2. Student 1: [12, 34], Student 2: [67, 90] -> Max pages = 67 + 90 = 157
  3. Student 1: [12, 34, 67], Student 2: [90] -> Max pages = 12 + 34 + 67 = 113
  • The minimum of these maximum pages is 113.

1. Dynamic Programming / Recursive Approach - O(N^2 * M)

Let minPages(arr, n, k) represent the minimum possible maximum pages to allocate n books to k students.

• Base Cases:
  • If k === 1, the only student gets all remaining books -> sum(0..n-1).
  • If n === 1, only 1 book exists -> arr[0].
• Recurrence: Try all possible splits i where the first k-1 students get first i books and the last student gets books from i to n-1: minPages(arr, n, k) = min( max(minPages(arr, i, k-1), sum(arr, i, n-1)) ) for all 1 <= i < n

function sum(arr, from, to) {
    let s = 0;
    for (let i = from; i <= to; i++) {
        s += arr[i];
    }
    return s;
}
 
function minPagesDP(arr, n, k) {
    if (k === 1) return sum(arr, 0, n - 1);
    if (n === 1) return arr[0];
 
    let res = Infinity;
 
    for (let i = 1; i < n; i++) {
        res = Math.min(
            res,
            Math.max(minPagesDP(arr, i, k - 1), sum(arr, i, n - 1))
        );
    }
 
    return res;
}

2. Optimized Binary Search Approach - O(N log(Sum - Max))

The most optimal way to solve the book allocation problem is using Binary Search on the Answer.

• Search Space:
  • Lower bound (low): max(pages) (since the student who gets the largest book must read at least that many pages).
  • Upper bound (high): sum(pages) (if only 1 student gets all books).
• Binary Search Strategy:
  • Find mid = Math.floor((low + high) / 2).
  • Check if it is possible to assign books to at most M students such that no student reads more than mid pages.
  • If possible, then mid is a potential solution. Try to find a smaller maximum by setting high = mid - 1.
  • Otherwise, increase capacity limit by setting low = mid + 1.

function isFeasible(arr, n, m, max_limit) {
    let studentsRequired = 1;
    let current_pages = 0;
 
    for (let i = 0; i < n; i++) {
        // If a single book has more pages than max_limit, allocation is impossible
        if (arr[i] > max_limit) return false;
 
        if (current_pages + arr[i] > max_limit) {
            studentsRequired++;
            current_pages = arr[i];
 
            if (studentsRequired > m) return false;
        } else {
            current_pages += arr[i];
        }
    }
 
    return true;
}
 
function allocateMinimumPages(arr, n, m) {
    if (m > n) return -1; // More students than books
 
    let low = Math.max(...arr);
    let high = arr.reduce((acc, curr) => acc + curr, 0);
    let ans = -1;
 
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
 
        if (isFeasible(arr, n, m, mid)) {
            ans = mid;
            high = mid - 1; // Try to find a smaller maximum
        } else {
            low = mid + 1; // Increase page capacity limit
        }
    }
 
    return ans;
}
 
// Driver code
const pages = [12, 34, 67, 90];
const students = 2;
console.log("Minimum maximum pages allocated:", allocateMinimumPages(pages, pages.length, students));
// Output: Minimum maximum pages allocated: 113

Complexity Analysis

• Time Complexity:
  • Recursive / DP approach: O(N^2 * M).
  • Binary Search approach: O(N * log(Sum - Max)) where Sum is the sum of all pages, and Max is the maximum page element.
• Space Complexity:
  • DP: O(N * M) auxiliary space to memoize.
  • Binary Search approach: O(1) auxiliary space.