Array Sorting Binary Search Two Pointers
Proficient Level

Implement the allocateMinimumPagesSimple method that minimizes the maximum pages assigned to any student.

The input contains an array pages, its length size, and the number of students. Each array value represents the number of pages in one book.

Your task is to allocate books to students in order, so each student receives a continuous group of books, and every book is assigned. The goal is to minimize the maximum number of pages assigned to any one student.

For example, for [12,34,67,90] and 2 students, the best allocation gives a maximum of 113 pages.

Example 1
Input:
pages (int[]) = [12,34,67,90]
size (int) = 4
students (int) = 2
Return:
(int) 113
Example 2
Input:
pages (int[]) = [10,20,30,40]
size (int) = 4
students (int) = 2
Return:
(int) 60
Example 3
Input:
pages (int[]) = [10,20,30]
size (int) = 3
students (int) = 1
Return:
(int) 60

Use binary search on the answer.

The minimum possible answer is the largest single book, because a book cannot be split. The maximum possible answer is the sum of all pages, where one student gets all books.

For each guessed maximum, check whether the books can be assigned to the given number of students without any student crossing that limit. If it is possible, try a smaller maximum. Otherwise, increase the limit.

Pseudocode:

function canAllocate(pages, size, students, limit):
    usedStudents = 1
    currentPages = 0
    for each bookPages in pages:
        if currentPages + bookPages > limit:
            usedStudents++
            currentPages = bookPages
        else:
            currentPages = currentPages + bookPages
    return usedStudents <= students
function allocateMinimumPagesSimple(pages, size, students):
    if students > size:
        return -1
    left = maximum value in pages
    right = sum of all pages
    answer = right
    while left <= right:
        mid = left + (right - left) / 2
        if canAllocate(pages, size, students, mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    return answer
Run your code to see the result.