🚌

Allocate a minimum number of pages (Hard)

Prerequisites: 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array ,🧩Monotonic function, 🐒KOKO eating Bananas

Question

Given a number of pages in different books and M students. The books are arranged in ascending order of the 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.

Geeks For Geeks

Example 1

pages = [10, 20, 30, 40] ,m(students) = 2
Output : 60

There are 2 number of students. Books can be distributed in following fashion 

first = 10 [10], second = 90 [20+30+40] # at max limit 90
first = 30 [10+20], second = 70 [30+40] # at max limit 70
first = 60 [10+20+30], second = 40 [40] # at max limit 60

Three ways to split

Max pages are 90,70 and 60, in which 60 is the minimum

Example 2

pages = [12,34,67,90], m(students) = 2 # The array is not always sorted
Output:113



first = 12 [12], second = 191 [34,67,90] # at max limit 191
first = 46 [12,34], second = 157 [67, 90] # at max limit 157
first = 113 [12,34,67], second = 90 [90] # at max limit 113

Max pages are 191,157 and 113, in which 113 is the minimum

Reframing the question

This question is riddled in multi-level complexity so let's reframe it by asking some questions.

What are the criteria for the allocation of books?

Every student must have at least one book.
Every student is assigned a set of consecutive books:

For an array [10, 20, 30, 40], the first set is 30 (10 + 20), and the second set is 70 (30 + 40).

Every student must have a unique book, two students can’t have the same book
It is important to note that the array in this question is not always sorted.

What are we trying to optimize twofold here.

We are trying to minimize (first optimality)

The maximum number of pages a student can be allocated (second optimality).

When we see an optimization problem the first thing we ask our self whether the optimization is around a monotonic range. In this case yes, if we increase the value of (x) maximum pages per student, the students needed (y)decreases. Similar to 🐒KOKO eating Bananas .

Let's examine the maximum pages allocated, increasing in ascending order. Let's see what we can learn.

Let's try allocating a maximum of 1 page to each student.

pages = [10, 20, 30, 40] ,m(students) = 2

first = []
second = []

12,20,30,40 # not possible

# can't allocate any books as the size of the books was too larger than our possible maximum

lets try 39

pages = [10, 20, 30, 40] ,m(students) = 2

first = [10,20]
second = [30] 
40 # not possible

# we can't allocate all books

Let's try 40 (the maximum value in the 'pages' array, which needs to be the minimum number of pages allocated to a student to allocate all the books). Although we successfully allocated the books to students, we exceeded the limit of 2 students.

pages = [10, 20, 30, 40] ,m(students) = 2


first = [10,20] 
second = [30] 
third = [40]
	
# we are out of our depth here as we need more than 2 students.

Increasing the number will reveal something uncertain about the question. Let's try 90.

pages = [10, 20, 30, 40] ,m (students) = 2


testing for 90 pages

first = [10,20,30] = 60 

second = [40] = 40 


Another combination

first = [10] = 10

second = [20+30+40] = 90


Another combination

first = [10,20] = 30

second = [30+40] = 70

...


Some numbers have multiple combinations

# all of these are combinations but there might be a lower maximum.

The allocation will become really complex once we increase the number of students. Will have to use some sort of recursion with Dynamic programming, but for this question, we will use a greedy approach. Here is the link if you want to study the recursive and Dynamic programming side of things with a similar question.
We will use the Greedy Approach, and see why it works.

Let’s try a few more values to understand this. Let's try 59

pages = [10, 20, 30, 40] , m (students) = 2

first = [10,20] # can't add 30 goes to next student
second = [30] # can't add 40 :( need one more student
third = [40]

and now 60

pages = [10, 20, 30, 40] ,m (students) = 2

first = [10,20,30] # can't add 30 goes to next student
second = [40] # can't add 40 :) need one more student

The first value where we were able to allocate all the books amongst m students, will allow us to minimize the maximum number of pages to m students

Will it be possible to allocate all the books with a different combination and have it be less than 60(or that first possible value.)
Let's see if there are more combinations for how we can allocate the books with a maximum of 60 pages amongst 2 students.

pages = [10, 20, 30, 40] ,m (students) = 2


first combination
first = [10] 
second = [20,30]
third = [40] # overshot  

second combination
first = [10,20] 
second = [30]
third = [40] # overshot  

one more 

first = [10] 
second = [20]
third = [30,40] # overshot ahh damn it

Is it possible to find and subarray that is not made by the first recurring items and we are able to allocate the books, something like the second and third combination in the above example?
Lets try an example.

pages = [1,9,4,9] m = 2

at 12 pages as max
first = [1,9] [4]# adding 9 will make it 13 and that is not possible 

at 13 pages as max
first = [1,9] [4,9] # adding 9 will be now possible.

Greedy proofs are always the hardest to prove, but we can try to make some sense of it.
Since this needs to be continuous allocation and all the subarrays are maxed out when we get the first combination(greedy way) we are able to allocate the books to 2 students.
What if we try another combination? We will break the maximization principle


at 12 pages as max
greedy = [1,9] [4] # adding 9 will make it 13 and that is not possible 
second = [1],[9,4] 

let's try with 13

at 13 pages as max
greedy = [1,9] [4,9] # adding 9 will be now possible.
second = [1][9,4][9]  # It is still not possible because we have exceeded the number of students, and we have already allocated the maximum number of books to each student at this value. Removing pages from a previous student's allocation would reduce the maximization and result in additional books being left over for the final allocation making the limit go over m students.

Brute Force Intuition + implementation

We are trying to find a minimum, but is it along a monotonic range? Yes, as we increase the number of maximum pages, the number of students required decreases, which is an essential characteristic of a monotonic function. So with the first value we reach the threshold of m students all values after that will allow us to allocate with m or less students but at a maximum page count that will be higher than the threshold that we achieved with our first value.

Now we have determined the question in the light of the Similar Questions in 🐒KOKO eating Bananas , we will move to our next step
The maximum number of pages being allocated to each student is still 0 to infinity. Can we reduce the range?

Yes, What is the minimum(max value of pages possible)? We need at least a maximum of max(pages) to allocate the book in the example below. If the maximum value for allocation is less than 40, as previously discussed, it will be impossible to allocate the book to any student.



For 39 as maximum
______________________
pages = [10, 20, 30, 40] ,m(students) = 2

first = [10,20]
second = [30] 
40 # not possible


For 40 as maximum
______________________
pages = [10, 20, 30, 40] ,m(students) = 2

first = [10,20] 
second = [30] 
third = [40]
	
# we are out of our depth here as we need more than 2 students, but we allocated all books successfully

What is the maximum (max value of pages possible)? The maximum possible answer is when there is only one student, as they will take all the maximum pages available. Any maximum above the sum of pages in this case 100 will be a waste, as all the books have already been allocated.

For 100 as maximum
________________________
pages = [10, 20, 30, 40] ,m(students) = 1

first = [10,20,30,40] 

For 101 as maximum
_______________________
pages = [10, 20, 30, 40] ,m(students) = 1

first = [10,20,30,40] 

#no change

So we can say that.

least = max(pages)
most = sum(pages)

The First Feasibility.

We try all the values from the least to the most and return the first which meets the threshold of m students.

least,most = max(pages),sum(pages)
minimumNumberOfMaxPages = -1

for maxPossible in range(least,most+1):
    if self.allBooksAllotedProperly(maxPossible,pages,m):
        return maxPossible

Calculating the feasibility. We are using a greedy approach to allocate student pages. We start allocating the books to the first student. Once the limit of PossibleMax (maximum pages a student can read) is reached, we allocate the same book to the next student. If we allocate the books within or less than the threshold of m students, we return True; otherwise, False.

    def allBooksAllotedProperly(self,possibleMax,pages,m): 
        
        numberOfStudentsUsed = 1
        totalPages = 0
        
        for book in pages:
            
            totalPages += book
            pagesWentOverOverMaximum = totalPages > possibleMax
            
            if pagesWentOverOverMaximum:
                
                numberOfStudentsUsed+=1
                # start with the new student
                # Add the book that didn't fit 
                # to that student
                totalPages = book
            
       
        return numberOfStudentsUsed <= m

Code (Brute Force)

class Solution:

    def findPages(self,pages, m):
        least,most = max(pages),sum(pages) 
        minimumNumberOfMaxPages = -1
        
        for maxPossible in range(least,most+1):
            if self.allBooksAllotedProperly(maxPossible,pages,m):
                return maxPossible
        
    def allBooksAllotedProperly(self,possibleMax,pages,m): 
        
        numberOfStudentsUsed = 1
        totalPages = 0
        
        for book in pages:
            
            totalPages += book
            pagesWentOverOverMaximum = totalPages > possibleMax
            
            if pagesWentOverOverMaximum:
                
                numberOfStudentsUsed+=1
                # start with the new student
                # Add the book that didn't fit 
                #to that student aswell
                totalPages = book
            
       
        return numberOfStudentsUsed <= m

Complexities

Time Complexity: O(N*M)

N = max(pages)

M = len(Pages)

Space Complexity: O(1)

If you look, we are using a nested for loop here. The outer loop iterates over all the possibleMax Pages from least to max(piles)(in the worst case least will be 1). With each iteration of that loop, we go over the whole pages array to check the feasibility of that PossibleMax. In the worst case, we might have to check all possible PossibleMaxes until we get a possible answer. Is there a way to do better?

Logarithmic Intuition

We discussed in 🐒KOKO eating Bananas similar questions session on how to look for if the question can be solved in logarithmic time.
When we reach the first possible maximum (pages), we can allocate all the books among m students. All subsequent possible maximums will be higher than the previous one, but still, allow us to allocate all books among m students. As we keep increasing possible maximums, we will never be in a situation where we cannot allocate all the books among m students.

This will insight will allow us to divide our space between a feasible and nonfeasible split. Talked in detail about in 🐒KOKO eating Bananas (Logrithmic Intuition 2.0 part 4.)

We can decide that solutions on one side of m are not possible and solutions on the other side are possible. To do this, we make a rule to classify values as possible or not. (I have not gone into detail here around how we chop different halves until we reach the first True Value look at 🐒KOKO eating Bananas (Logarithmic Intuition 2.0 part 4 )

Applying the feasibility criteria we are able to reduce the problem to 🔑Find the First True in a Sorted Boolean Array

Once you understand how to separate the feasibility part of the solution, the optimization can be achieved through a regular binary search on a Boolean array. Decomposing the problem in this way helps to simplify it.

Comparison

Code for First True in a sorted Boolean array

class Solution:

    def firstTrue(self, bools):

        


				(left, right) = (0, len(bools) - 1)
        possibleValue = -1

        while left <= right:

            mid = left + (right - left) // 2
						
					# True
            if bools[mid]: 
                possibleValue = mid
                right = mid - 1
						
					# False
            else:
                left = mid + 1

        return possibleValue

Code For Allocate Books

class Solution:

    def findPages(self,pages, m):
        # if there are less books than students
				if len(pages) < m: 
            return -1  #< -change here

        least,most = max(pages),sum(pages)  #<-change here
        minimumNumberOfMaxPages = -1
       
        while least <= most:
            
            possibleMax = least + (most-least)//2 
            
            # True  # v-change here
            if self.allBooksAllotedProperly(possibleMax,pages,m):
                minimumNumberOfMaxPages =  possibleMax 
                most = possibleMax - 1 # reduce Possible Max
            
			     #False
            else: 
                least = possibleMax + 1 # increase Possible Max
              
                
        return minimumNumberOfMaxPages
          


    def allBooksAllotedProperly(self,possibleMax,pages,m): #<-change here
        
        numberOfStudentsUsed = 1
        totalPages = 0
        
        for book in pages:
            
            totalPages += book
            pagesWentOverOverMaximum = totalPages > possibleMax
            
            if pagesWentOverOverMaximum:
                
                numberOfStudentsUsed+=1
                # start with the new student
                # Add the book that didn't fit 
                #to that student aswell
                totalPages = book
            
       
        return numberOfStudentsUsed <= m

Sandbox—PythonTutor (Visualized)

Select a certain line such as (if self.allBooksAllotedProperly(possibleMax,pages,m):) to see how the value changes around that, instead of going over all 400 steps.“

Time Complexity

`O(M * log(N)) N =` `max(Pages)`

N = max(pages)

M = len(pages)

The feasibility function still needs to iterate over M times, but we can reduce the number of times we need to check for the optimal value from n to log(n).

📐Understanding Time Complexity of OLog(N): Math + Intuition

Code For Allocate Books

class Solution:

    def findPages(self,pages,m):
        # if there are less books than students
				if len(pages) < m: 
            return -1  

        least,most = max(pages),sum(pages)
        minimumNumberOfMaxPages = -1
       
        while least <= most:
            
            possibleMax = least + (most-least)//2 
            
            # True  
            if self.allBooksAllotedProperly(possibleMax,pages,m):
                minimumNumberOfMaxPages =  possibleMax 
                most = possibleMax - 1 # reduce Possible Max
            
			     #False
            else: 
                least = possibleMax + 1 # increase Possible Max
              
                
        return minimumNumberOfMaxPages
          


    def allBooksAllotedProperly(self,possibleMax,pages,m): #<-change here
        
        numberOfStudentsUsed = 1
        totalPages = 0
        
        for book in pages:
            
            totalPages += book
            pagesWentOverOverMaximum = totalPages > possibleMax
            
            if pagesWentOverOverMaximum:
                
                numberOfStudentsUsed+=1
                # start with the new student
                # Add the book that didn't fit 
                #to that student aswell
                totalPages = book
            
        
        
        
        return numberOfStudentsUsed <= m

Code For Split Array Largest Sum

class Solution:

    def splitArray(self, nums, m):
       
        if len(nums) < m:  # < -change here
            return -1 

        least,most = max(nums),sum(nums)  #<-change here
        minimizedLargestSum = -1
       
        while least <= most:
            
            possibleMax = least + (most-least)//2 
            
            # True  # v-change here
            if self.allNumbersSplitProperly(possibleMax,nums,m):
                minimizedLargestSum =  possibleMax 
                most = possibleMax - 1 # reduce Possible Max
            
			     #False
            else: 
                least = possibleMax + 1 # increase Possible Max
              
                
        return minimizedLargestSum
          


    def allNumbersSplitProperly(self,possibleMax,nums,m): #<-change here
        
        numberOfSplits = 1
        totalSum = 0
        
        for num in nums:
            
            totalSum += num
            sumWentOverOverMaximum = totalSum > possibleMax
            
            if sumWentOverOverMaximum:
                
                numberOfSplits+=1
                # start with the new student
                # Add the book that didn't fit 
                #to that student aswell
                totalSum = num
            
        
        
        
        return numberOfSplits <= m

Thanks for sticking this long, Appreciate it!

Dedication—This question is dedicated to these gentlemen who made a difficult task less difficult!

These resources cover what has been discussed and more. They can be a great starting point for your journey into learning about binary search.

💡

Allocate a minimum number of pages (Hard)

Prerequisites: 🍦Binary Search(Vanilla) , 🔑Find the First True in a Sorted Boolean Array ,🧩Monotonic function, 🐒KOKO eating Bananas

Question

Geeks For Geeks

Reframing the question

Brute Force Intuition + implementation

Code (Brute Force)

Complexities

Logarithmic Intuition

Comparison

Code for First True in a sorted Boolean array

Code For Allocate Books

Sandbox—PythonTutor (Visualized)

Time Complexity

O(M * log(N)) N = max(Pages)

Similar Questions

Code For Allocate Books

Code For Split Array Largest Sum

Dedication—This question is dedicated to these gentlemen who made a difficult task less difficult!

`O(M * log(N)) N =` `max(Pages)`