Searching: Allocate minimum pages

Problem Statement:

You are given an array that represents number of pages in the ith book.

There are m students, you need to allocate all the books to all the students.

Below are the constraints:

1. Each students gets at least one book.

2. Books are allocated in continuous sequence

3. The maximum number of pages assigned to any students is minimized

4. Each book should be allocated to only one student

Example:

Input arr = [10, 20, 30, 40] m = 2

Output: 60

The books can be distributed in following ways:

[10] and [20, 30, 40] - Maximum pages assigned to a student is 20 + 30 + 40 = 90

[10, 20] and [30, 40] - Maximum pages assigned to a student is 30 + 40 = 70

[10, 20, 30] and [40] - Maximum pages assigned to a student is 10 + 20 + 30 = 60

hence the 3rd option has minimum pages assigned to a student

Solution : Binary Search

We will solve the problem using binary search.

Time Complexity: O(N * log(sum(arr[])-max(arr[])+1))
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <numeric>

using namespace std;

int solution(vector<int>& arr, int k) 
{
    int n = arr.size();
    if (k > n) 
    	return -1;
    int low = *max_element(arr.begin(), arr.end());
    int high = accumulate(arr.begin(), arr.end(), 0);

    while (low < high) 
    {
        int mid = (low + high) / 2;
        int students = 1;
        int sum = 0;
        for (int pages : arr) 
        {
            if ((sum += pages) > mid)
            {
            	students++;
            	sum = pages;
            }
        }
        if (students > k) 
        	low = mid + 1;
        else 
        	high = mid;
    }
    return low;
}

int main()
{
    vector<int> arr = {12, 34, 67, 90};

    int m = 2;

    cout <<solution(arr, m) << "\n";
    return 0;
}

Output

113