Allocate Books

Problem statement

Given an array ‘arr’ of integer numbers, ‘arr[i]’ represents the number of pages in the ‘i-th’ book. There are ‘m’ number of students, and the task is to allocate all the books to the students.(link)

Allocate books in such a way that: (3 condtions)

1. Each student gets at least one book.

2. Each book should be allocated to only one student.

3. Book allocation should be in a contiguous manner.

You have to allocate the book to ‘m’ students such that the maximum number of pages assigned to a student is minimum. If the allocation of books is not possible, return -1.

Leetcode - link

Example:

Input: ‘n’ = 4 ‘m’ = 2 
‘arr’ = [12, 34, 67, 90]
Output: 113

Explanation: All possible ways to allocate the ‘4’ books to '2' students are:

1. 12 | 34, 67, 90 - the sum of all the pages of books allocated to student 1 is ‘12’, and student two is ‘34+ 67+ 90 = 191’, so the maximum is ‘max(12, 191)= 191’.

2. 12, 34 | 67, 90 - the sum of all the pages of books allocated to student 1 is ‘12+ 34 = 46’, and student two is ‘67+ 90 = 157’, so the maximum is ‘max(46, 157)= 157’.

3. 12, 34, 67 | 90 - the sum of all the pages of books allocated to student 1 is ‘12+ 34 +67 = 113’, and student two is ‘90’, so the maximum is ‘max(113, 90)= 113’.

We are getting the minimum in the last case. Hence answer is ‘113’.

Solution

To address problems involving the minimum or maximum, a common strategy is to initially solve them using a brute-force approach. This enables the derivation of an optimized version of the problem.

The problem specifies three conditions, with one crucial requirement being the contiguous assignment of books.

The objective is to allocate books in a manner that minimizes the maximum number of pages assigned to any individual.

Answer Range: Determining the range is straightforward by considering edge cases.

Scenario 1 - When the number of books is equal to the number of individuals, each book is assigned to a respective person. The solution for this scenario is the maximum number of pages in the given array.

Scenario 2 - In the case of a single individual, the maximum pages allocated to them would be the sum of all pages in the given array.

In essence, our potential answer falls between the maximum value and the total sum of the array. This range is established because an individual can take up at least one book and at most all available books.

Answer Range: [max(arr), sum(arr)]

Brute force Approach

In this methodology, we systematically examine each value within the specified answer range. We determine the number of individuals needed when the maximum number of pages assigned to an individual is fixed. If the required number of individuals matches the given count, we return the solution.

Counting Individuals: With a given maximum value 'k', we continuously allocate books to individuals until the sum reaches the maximum value 'k'. The count is incremented iteratively until all the books are assigned

Time - O(N * (sum(arr[])-max(arr[])+1)),

where N = size of the array, sum(arr[]) = sum of all array elements, max(arr[]) = maximum of all array elements.

Space - O(1)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Solution {
    public static int findPages(ArrayList<Integer> arr, int n, int m) {

        if(arr.size()<m) return -1;

        int startValue = Collections.max(arr);
        int endValue = arr.stream().mapToInt(Integer::intValue).sum();


        for(int i=startValue; i<=endValue; i++){
            int personsRequired = countPersons(arr, i);
            if(personsRequired==m) return i;
        }

        return low;

    }

    public static int countPersons(ArrayList<Integer> arr, int k){

        int count = 1;

        int personPages = 0;

        for(int pages: arr){

            if(personPages + pages <=k){
                personPages+= pages;
            } else{
                personPages = pages;
                count+=1;
            }
        }
        return count;
    }
}

Optimal Approach - Binary Search

Our answer range is in sorted order we can apply binary search.

Core Logic: Observing the trend in the answer range, we notice a reduction in the number of individuals required for the entire book allocation as the maximum pages an individual can possess increases. This underlying pattern is leveraged in our approach. Placing our low and high markers at the extremes of the answer range, we calculate the midpoint (mid) and determine the number of persons required for this mid value. We adjust the markers accordingly.

• If the countPersons for the mid value is less than the given number of persons, we shift the high marker to the left, i.e., high = mid - 1, as more individuals are required on the left end.

• Else, if countPersons of mid is greater than or equal to the given number of persons, we move the low marker towards the right, i.e., low = mid + 1.

The result is directly obtained from the low value because initially, it is positioned on a value that doesn't meet the criteria, while the high points to a value that only partially satisfies the condition (requiring only one person). Following the search, low points to a valid answer, and high points to an invalid one. If the mid value yields the same number of persons as the required answer, we still shift the high towards the left, as there might be a smaller value than mid that also satisfies the condition.

Time - O(N * log(sum(arr[])-max(arr[])+1)),

where N = size of the array, sum(arr[]) = sum of all array elements, max(arr[]) = maximum of all array elements.

Space - O(1)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Solution {
    public static int findPages(ArrayList<Integer> arr, int n, int m) {

        if(arr.size()<m) return -1;
        int startValue = Collections.max(arr);
        int endValue = arr.stream().mapToInt(Integer::intValue).sum();

        int low = startValue;
        int high = endValue;

        while(low<=high){
            int mid = (low+high)/2;

            if(countPersons(arr, mid)<=m){
                high = mid - 1;
            }else{
                low = mid + 1;
            }

        }
        return low;
    }

    public static int countPersons(ArrayList<Integer> arr, int k){

        int count = 1;

        int personPages = 0;

        for(int pages: arr){

            if(personPages + pages <=k){
                personPages+= pages;
            } else{
                personPages = pages;
                count+=1;
            }
        }

        return count;

    }
}