Allocate Minimum Pages | Practice Hard 0 attempts
GeeksforGeeks ↗

Allocate Minimum Pages | Practice

Hard Sorting&Searching GeeksforGeeks

Given an array of N integers where arr[i] is the number of pages in the ith book, allocate books to M students such that the maximum pages assigned to any student is minimized. Each student gets at least one book, and books are contiguous.

Example: arr = [12, 34, 67, 90], M = 2 → Output: 113

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^5
  • 1 <= A[i] <= 10^6
  • 1 <= M <= N
Test Cases
Case 1
Args: [[12,34,67,90],2] Expected: 113
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.

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