Allocate_Minimum_Pages.java

/*

Given an array arr[] of integers, where each element arr[i] represents the number of pages in the i-th book.
You also have an integer k representing the number of students. 
The task is to allocate books to each student such that:

Each student receives atleast one book.
Each student is assigned a contiguous sequence of books.
No book is assigned to more than one student.
All books must be allocated.
The objective is to minimize the maximum number of pages assigned to any student. 
In other words, out of all possible allocations, find the arrangement where the student who receives the most pages still has the smallest possible maximum.
If it is not possible to allocate books to all students, return -1;

Note: Test cases are generated such that the answer always fits in a 32-bit integer.

Examples:

Input: arr[] = [12, 34, 67, 90], k = 2
Output: 113
Explanation: Allocation can be done in following ways:
=> [12] and [34, 67, 90] Maximum Pages = 191
=> [12, 34] and [67, 90] Maximum Pages = 157
=> [12, 34, 67] and [90] Maximum Pages = 113.
The third combination has the minimum pages assigned to a student which is 113.

Input: arr[] = [15, 17, 20], k = 5
Output: -1
Explanation: Since there are more students than total books, it's impossible to allocate a book to each student.
Constraints:
1 ≤ arr.size() ≤ 106
1 ≤ arr[i], k ≤ 104



*/

class Allocate_Minimum_Pages {
    public boolean allotment(int[] arr, long limit, int k) {
        int n = arr.length;
        int student = 1;
        long pages = arr[0];

        for (int i = 1; i < n; i++) {
            pages = pages + arr[i];

            if (pages <= limit) {
                continue;
            } else {
                student++;
                pages = arr[i];
            }
        }

        return student <= k;
    }

    public int findPages(int[] arr, int k) {
        int n = arr.length;

        if (k > n) {
            return -1;
        }

        long res = -1;
        long sum = 0;
        long max = Long.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            max = Math.max(max, arr[i]);
            sum = sum + arr[i];
        }

        long low = max;
        long high = sum;

        while (low <= high) {
            long guess = low + (high - low) / 2;

            if (allotment(arr, guess, k)) {
                res = guess;
                high = guess - 1;
            } else {
                low = guess + 1;
            }
        }

        return (int) res;
    }
}