Allocate Minimum Pages | Practice Hard 0 attempts
GeeksforGeeks ↗

Allocate Minimum Pages | Practice

Hard Sorting&Searching GeeksforGeeks

You're given an array arr of N integers, where arr[i] is the page count of the i-th book, and you need to distribute these books among M students. Books must be handed out in the order they appear — each student gets a contiguous block — and every student must receive at least one book. Choose an allocation that minimizes the largest number of pages any single student ends up with, and return that minimized maximum.

Return -1 if there are more students than books, because every student must receive at least one book.

Input Format
Implement allocateMinimumPages(arr, m). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
arr = [12,34,67,90]
m = 2
Output
113

Example 2

Input
arr = [10]
m = 2
Output
-1
Constraints
  • 1 <= N <= 10^5
  • 1 <= A[i] <= 10^6
  • 1 <= M <= 10^5
Test Cases (2)
Case 1
Args: [[12,34,67,90],2] Expected: 113
Case 2
Args: [[10],2] Expected: -1
Topics
Sorting&Searching

Binary Search on Answer

Binary search on the maximum pages. For each candidate, greedily check if M students can read all books.

javascript
function allocateMinimumPages(arr, m) {
  if (m > arr.length) return -1;
  let lo = Math.max(...arr), hi = arr.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    let students = 1, pages = 0;
    for (const p of arr) {
      if (pages + p > mid) { students++; pages = p; }
      else pages += p;
    }
    if (students <= m) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Time: O(N log S) where S = sum of pages | Space: O(1)

Saved in this browser only. Private to you.

JavaScript