Book Allocation Problem

Introduction

In this article, we will solve the problem: Book Allocation. We will start with a quite naive and intuitive approach and then proceed towards a more optimal binary search solution. 

Let’s start with the problem statement.

Problem Statement

Given an array ‘pages’ of integer numbers, where ‘pages[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 their students. 

Allocate books in a way such that:

1. Each student gets at least one book.

2. Each book should be allocated to a student.

3. Book allocation should be in a contiguous manner.

You have to allocate the books to ‘m’ students such that the maximum number of pages assigned to a student is minimum.

Please try to solve this problem on your own before moving on to further discussion here.

Let’s understand the problem statement through an example.

Example: 

Number of books = 4 and Number of students = 2

pages[] = { 10,20,30,40}

Important points to consider

  • Assign at least one book to every student, so there can’t be any allocation such that a student gets no books assigned.
  • While allocating the books, no book should be left out. In other words, you have to allocate each and every book given.
  • Allocate in a contiguous manner. Let's say you have to allocate 3 books to a student from pages[] = { 10,20,30,40}

 

Then, the possible allocations can be - {10,20,30} and {20,30,40}. You can’t allocate {10,30,40} as it is not contiguous.

All possible ways of book allocation are shown in the below figure-

The minimum of the maximum number of pages assigned = min{90,70,60} = 60. Hence, the required answer is 60.

Brute Force Approach

Let be the number of books and the number of students.

In the case of M > N:

Simply return -1 as the number of students is greater than the number of books available, and according to the given constraints, it is not possible to allocate at least one book to each student.

 Let’s see the algorithm for all other cases where M<=N:

  • We have to minimize the value of the maximum number of pages assigned to a student in an allocation. 
  • If the maximum number of pages assigned to a student in a book allocation is max_pages, then this implies that the number of pages assigned to every student is less than or equal to max_pages.
  • Let’s focus on the possible values of the number of pages that can be assigned to a student? 
  • The minimum value can be equal to 0 (Though not in this problem because you have to assign each student at least one book, so the number of pages can't be zero)
  • The maximum number of pages will be the sum of the number of pages in all books. (This will happen when you assign all the books to one student).
  • The range of the maximum number of pages we obtained is - (0, sum of all the values of pages array]. Open interval on 0 because at least one book needs to be assigned to every student. So, the interval we get is [1, sum of pages array].

Steps of algorithm

  1. Iterate over all values ranging from numPages=1 to numPages=sum of pages array.
  2. Check if it is possible to allocate the books such that the value of the number of pages assigned to any student is less than or equal to numPages in each iteration.
  3. If the maximum number of pages can be equal to numPages, then return numPages as the answer. We don’t need to iterate further because after this the value of numPages will increase, but we are interested in finding the minimum value of the maximum number of pages that can be allocated. 

 

How to check if it is possible to allocate the books such that the maximum number of pages assigned to any student is numPages?

  1. Initialize count of students with 1.
  2. Keep allocating the books to a student until the sum of the pages assigned is less than numPages. 
  3. If at any point the number of pages assigned to a student exceeds numPages, then allocate the current book to the next student and increment the count of students.
  4. If the count of students becomes greater than M, then return false.
  5. In the end, if the count of students is equal to M, return true. 

Implementation in C++

/* C++ code for Book Allocation problem to find the minimum value of the maximum
number of pages*/
#include <bits/stdc++.h>

using namespace std;
/*function to check if it is possible to allocate the books such that the
maximum number of pages assigned to any student is numPages*/
bool isPossible(int pages[], int n, int m, int numPages) {
    int cntStudents = 1;
    int curSum = 0;
    for (int i = 0; i < n; i++) {
        if (pages[i] > numPages) {
            return false;
        }
        if (curSum + pages[i] > numPages) {
            /* Increment student count by '1'*/
            cntStudents += 1;
            /* assign current book to next student and update curSum */
            curSum = pages[i];
            /* If count of students becomes greater than given no. of students, return False*/
            if (cntStudents > m) {
                return false;
            }
        } else {
            /* Else assign this book to current student and update curSum */
            curSum += pages[i];
        }
    }
    return true;
}
int allocateBooks(int pages[], int n, int m) {
    /* If number student is more than number of books */
    if (n < m) {
        return -1;
    }
    /* Count total number of pages */
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += pages[i];
    }
    /* Check for every possible value */
    for (int numPages = 1; numPages <= sum; numPages++) {
        if (isPossible(pages, n, m, numPages)) {
            return numPages;
        }
    }
    return -1;
}
int main() {
    int n = 4;
    int m = 2;
    int pages[] = {10, 20, 30, 40};
    cout << "The minimum value of the maximum number of pages in book allocation is: " << allocateBooks(pages, n, m) << endl;
}

 

Output:

The minimum value of the maximum number of pages in book allocation is: 60

 

Implementation in Python

def isPossible(arr, n, m, curr_min):
    cntStudents = 1
    curSum = 0
# iterate over all the books
    for i in range(n):
         if (arr[i] > curr_min):
             return False
        # Increment student count by '1'
         if (curSum + arr[i] > curr_min):
             cntStudents += 1
        # assign current book to next student and update curSum
             curSum = arr[i]
        # If count of students becomes greater than
        # given no. of students, return False
    # update curSum
         if (cntStudents > m):
            return False
         else:
            curSum += arr[i]
    return True
# function to find minimum pages
def allocateBooks(arr, n, m):
    sum = 0
# If number student is more than number of books
    if (n < m):
        return -1
# Count total number of pages
    for i in range(n):
        sum += arr[i]
    for numPages in range(1, sum+1):
        ans = isPossible(arr, n, m, numPages)
        if (ans):
            return numPages
    return -1

# Number of pages in books
arr = [10, 20, 30, 40]
n = len(arr)
m = 2  # No. of students
print("The minimum value of the maximum number of pages in book allocation is",
      allocateBooks(arr, n, m))

 

Output:

The minimum value of the maximum number of pages in book allocation is 60

 

Implementation in Java

public class Main {
    //function to check if it is possible to allocate the books such that the 
    //maximum number of pages assigned to any student is numPages
    static boolean isPossible(int arr[], int n, int m, int curr_min) {
        int cntStudents = 1;
        int curSum = 0;

        // iterate over all the books
        for (int i = 0; i < n; i++) {

            if (arr[i] > curr_min)
                return false;

            if (curSum + arr[i] > curr_min) {

                //Increment student count by '1'
                cntStudents++;

                /* assign current book to next student and update curSum */
                curSum = arr[i];

                /* If count of students becomes greater than given no. of students, return False*/
                if (cntStudents > m)
                    return false;
            }
            /* Else assign this book to current student and update curSum */
            else
                curSum += arr[i];
        }
        return true;
    }

    // method to find minimum pages
    static int findPages(int arr[], int n, int m) {
        long sum = 0;

        /* If number student is more than number of books */
        if (n < m)
            return -1;

        /* Count total number of pages */
        for (int i = 0; i < n; i++)
            sum += arr[i];

        for (int numPages = 1; numPages <= sum; numPages++) {
            if (isPossible(arr, n, m, numPages)) {
                return numPages;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int arr[] = {10, 20, 30, 40};
        int m = 2; //No. of students
        int n = 4;
        System.out.println("The minimum value of the maximum number of pages in book allocation is " + findPages(arr, n, m));
    }
}

 

Output:

The minimum value of the maximum number of pages in book allocation is 60

 

Complexity Analysis

Time Complexity - O(n*Sum)

O(n*Sum), where ‘n’ is the number of integers in the array ‘pages’ and ‘Sum’ is the sum of all the elements of ‘pages’.

We are using two nested loops of size ‘Sum’ and ‘n’. So, the time complexity is O(n*Sum).

Space Complexity - O(1)

O(1) as we are using constant space.

Binary Search Approach

The idea is to use binary search over the search space [1, Sum of pages array] to improve the time complexity.

Steps of algorithm

  • Initially ‘start = 0’ and ‘end = sum of all pages’ 
  • Find mid = (start+end)/2
  • Check if it is possible to allocate books such that the number of pages allocated to each student is less than or equal to mid.
  • If possible then:
    • Update the minimum answer found so far and put end mid-1.
    • Since we need the minimum value of the maximum number of pages, the end is set as mid-1 so that our search space now becomes [start,mid-1] to get a value less than mid.
       
  • Else 
    • Update start mid+1. Because if it is not possible to allocate the books with maximum pages equal to mid then it won’t be possible for any value less than mid. So, the search space becomes [mid+1,end].
  • Repeat the above steps until start <= end.

Implementation in C++

/* C++ code for Book Allocation problem to find the minimum value of the maximum number of pages*/ #include <bits/stdc++.h>

using namespace std;
/*function to check if it is possible to allocate the books such that the maximum number of pages assigned to any student is numPages*/
bool isPossible(int pages[], int n, int m, int numPages) {
    int cntStudents = 1;
    int curSum = 0;
    for (int i = 0; i < n; i++) {
        if (pages[i] > numPages) {
            return false;
        }
        if (curSum + pages[i] > numPages) {
            /* Increment student count by '1'*/
            cntStudents += 1;
            /* assign current book to next student and update curSum */
            curSum = pages[i];
            /* If count of students becomes greater than given no. of students, return False*/
            if (cntStudents > m) {
                return false;
            }
        } else {
            /* Else assign this book to current student and update curSum */
            curSum += pages[i];
        }
    }
    return true;
}
int allocateBooks(int pages[], int n, int m) {
    /* If number student is more than number of books */
    if (n < m) {
        return -1;
    }
    /* Count total number of pages */
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += pages[i];
    }
    /* Initialize start with 0 and end with sum */
    int start = 0, end = sum;
    int result = INT_MAX;
    /* Traverse until start <= end , binary search */
    while (start <= end) {
        /* Check if it is possible to distribute books by using mid as current maximum */
        int mid = start + (end - start) / 2;
        if (isPossible(pages, n, m, mid)) {
            result = min(result, mid); /*update the result*/
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return result;
}
int main() {
    int n = 4;
    int m = 2;
    int pages[] = {10, 20, 30, 40};
    cout << "The minimum value of the maximum number of pages in book allocation is: " << allocateBooks(pages, n, m) << endl;
}

 

This video gives a detailed tutorial of the “Book Allocation Problem”, so you can watch this video to understand it better.

 

Output:

The minimum value of the maximum number of pages in book allocation is: 60

 

Implementation in Python

# function to check if it is possible to allocate the books such that the
# maximum number of pages assigned to any student is numPages
def isPossible(arr, n, m, curr_min):
    cntStudents = 1
    curSum = 0
# iterate over all the books
    for i in range(n):
        if (arr[i] > curr_min):
            return False
        if (curSum + arr[i] > curr_min):
        # Increment student count by '1'
            cntStudents += 1
        # assign current book to next student and update curSum
        # If count of students becomes greater than
        # given no. of students, return False
            curSum = arr[i]
        if (cntStudents > m):
    # update curSum
            return False
        else:
            curSum += arr[i]
    return True
# function to find minimum pages
def allocateBooks(arr, n, m):
    sum = 0
# If number student is more than number of books
    if (n < m):
        return -1
# Count total number of pages
    for i in range(n):
        sum += arr[i]
# Initialize start with 0 and end with sum
    start, end = 0, sum
    result = 10**9
# Traverse until start <= end , binary search
    while (start <= end):
        mid = (start + end) // 2
        if (isPossible(arr, n, m, mid)):
            result = mid
            end = mid - 1
        else:
            start = mid + 1
    return result

# Number of pages in books
arr = [10, 20, 30, 40]
n = len(arr)
m = 2  # No. of students
print("The minimum value of the maximum number of pages in book allocation is",
      allocateBooks(arr, n, m))

 

Output:

The minimum value of the maximum number of pages in book allocation is 60

 

Implementation in Java

public class Main
{
	//function to check if it is possible to allocate the books such that the 
	//maximum number of pages assigned to any student is numPages
	static boolean isPossible(int arr[], int n, int m, int curr_min)
	{
		int cntStudents = 1;
		int curSum = 0;
	
		// iterate over all the books
		for (int i = 0; i < n; i++)
		{
		
			if (arr[i] > curr_min)
				return false;
	
			if (curSum + arr[i] > curr_min)
			{
		
		        //Increment student count by '1'
				cntStudents++;
				
				/* assign current book to next student and update curSum */
				curSum = arr[i];
				
				/* If count of students becomes greater than given no. of students, return False*/
				if (cntStudents > m)
					return false;
			}
			/* Else assign this book to current student and update curSum */
			else
				curSum += arr[i];
		}
		return true;
	}
	
	// method to find minimum pages
	static int findPages(int arr[], int n, int m)
	{
		long sum = 0;
	
	    /* If number student is more than number of books */
		if (n < m)
			return -1;
	
	    /* Count total number of pages */
		for (int i = 0; i < n; i++)
			sum += arr[i];
	
	    /* Initialize start with 0 and end with sum */
		int start = 0, end = (int) sum;
		int result = Integer.MAX_VALUE;
	
	    /* Traverse until start <= end , binary search */
		while (start <= end)
		{
			/* Check if it is possible to distribute books by using mid as current maximum */
			int mid = (start + end) / 2;
			if (isPossible(arr, n, m, mid))
			{
				result = mid;
				end = mid - 1;
			}
	
			else
				start = mid + 1;
		}
	
		return result;
	}
	
	public static void main(String[] args)
	{
		int arr[] = {10,20,30,40};
		int m = 2; //No. of students
	    int n=4;
		System.out.println("The minimum value of the maximum number of pages in book allocation is " +findPages(arr,n, m));
	}
}

 

Output:

The minimum value of the maximum number of pages in book allocation is 60

 

Complexity Analysis

Time Complexity - O(N*log(Sum))

O(N*log(Sum)), where ‘N’ is the number of integers in the array ‘pages’ and ‘Sum’ is the sum of all the elements of ‘pages’ as for every number ‘mid’ we have an iteration loop of size ‘N’ and binary search takes ‘log(Sum)’ time.

Space Complexity - O(1)

O(1) as we are using constant space.

Frequently Asked Questions

Does a greedy algorithm always work?

No, a greedy algorithm does not always work. To solve a problem via a greedy algorithm, you need to have intuitive proof in your mind, at least to lead to the correct solution. To show when it doesn’t work, you can think of a counter-example that will help rule out the greedy algorithm.

What is a comparator?

Comparator is an important concept. It is a function object that helps to achieve custom sorting depending on the problem requirements. 

What are the benefits of the greedy approach?

The Benefits of a Greedy Approach
    1. The algorithm is simpler to explain.
    2. This algorithm has the potential to outperform other algorithms (but, not in all cases).

Conclusion

In this article, we discussed the Book Allocation problem to find the minimum value of the maximum number of pages assigned to a student.

This question is one of the excellent applications of Binary Search.  We discussed the naive approach first and then optimized the solution by binary search as the problem had monotonic property. 

With this problem, you must have got an idea of when and how to use binary search.

Some of the problems which you can practice based on a similar concept are-  

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!

Was this article helpful ?
4 upvotes