Allocate Minimum Number of Pages

Problem statement

You are given an array of integers of size N, which represents the number of pages in N books. You are also given one integer M which represents the number of students. You have to distribute the N books to these M students for reading in such a way that every student has to read the book, and all the books should be read. One student can read more than one book also, but the books should be in continuous order. The order of the books will be ascending order according to the number of pages.

Your task is to distribute the books among the students in such a way that the maximum number of pages allocated to a student should be a minimum.

For example:

Let N=5 and M=3

Pages[] = { 120,132,165,324,987}

In the above example, we can have the following possibilities:

Case1:

Case3:

Case3:

Case4:

Case5:

Here, we will use binary search to get the solution to the problem.

We have a lot of edge cases in this problem like:

• If the number of books is less than students, then we can't determine any solution, and we will return -1.
• If the number of books equals to the number of students, then the answer would be the maximum of the array.
• If the number of students is 1, then the sum of the array would be the answer.

So as we know, we apply the binary search where we have the range of possible answers.

In this problem, the minimum answer would be the maximum value of the array, and the maximum answer would be the sum of the array.

Java Code:

Output:

Explanation

In the above code, we have implemented the binary search solution for minimum page allocation. We have the page array, which contains five values, and we have m equal to 2.

For binary search left = 987 and right = sum (page) = 1728

mid= 987+(1728-987)/2 = 1357

Now for the value mid, we will check that it is possible to allocate the pages in such a way that the maximum pages allocated to a student should be less than the mid.

So we will get true, and now our left=987 and right will be mid-1 which will be 1356.

Now mid= 987+(1356-987)/2 = 1171

So now, for the mid value 1171, we will get the true from the function, and we will move towards the left into search space. So right will be 1170 now.

Mid = 987+(1170-987)/2 = 1078

So now for value mid, we will get true, and we will move towards left, so right=1077

Mid=987+(1077-987)/2 = 1032

So we will true for 1032, so we will go towards left again. So right = 1031

Mid= 987+(1031-987)/2 = 1009

So we will return true again now, right = 1008

And mid= 987+(1008-987)/2 = 997

And function will return true for 997, so the right will be 996.

Mid = 987+(996-987)/2 = 991

And it is also true, so right = 990

Now mid = 987+(990-987)/2=988

And again, true, so right = 987

Now mid =987, and we will get true, so right=986 but left 987, so the loop will be terminated, and mid =987 will remain the answer.

Time complexity: O(logN), where N represents the total number of pages in the book.

Space complexity: O(1)