Allocate minimum number of pages JAVA

Allocate minimum number of pages JAVA

  June 06, 2017    

---

Problem : Given number of pages in n different books and m students. The books are arranged in ascending order of number of pages. Every student is assigned to read some consecutive books. The task is to assign books in such a way that the maximum number of pages assigned to a student is minimum.

Asked in Google Interview

import java.util.*;
import java.lang.*;
import java.io.*;
class minpage
 {
     public static boolean isPossible(int arr[],int n,int m,int curr_min)
     {
         int i;
         int curr_sum=0;
         int studentsRequired=1;
          for ( i = 0; i < n; i++)
    {
        if (arr[i] > curr_min)
            return false;

        if (curr_sum + arr[i] > curr_min)
        {
            studentsRequired++;
            curr_sum = arr[i];

            // if students required becomes greater
            // than given no. of students,return false
            if (studentsRequired > m)
                return false;
        }

        // else update curr_sum
        else
            curr_sum += arr[i];
    }
    return true;
     }
     public static int find(int arr[],int n,int m)
     {
         int start,end;
         start=end=0;
         int result=Integer.MAX_VALUE;
         if(n<m)
         return -1;
         for(int i=0;i<n;i++)
         end+=arr[i];
         while (start <= end)
    {
        int mid = (start + end) / 2;
        if (isPossible(arr, n, m, mid))
        {
            // if yes then find the minimum distribution
            result = Math.min(result, mid);
            end = mid - 1;
        }
        else
        start=mid+1;
     }
     return result;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int n=ab.nextInt();
   int arr[]=new int[n];
   for(int i=0;i<n;i++)
   arr[i]=ab.nextInt();
   int m=ab.nextInt();
   System.out.println(find(arr,n,m));
}
}
}