Given the number of pages in N different books and M students. Every student is assigned to read some books that can be consecutive or non-consecutive. The task is to assign books so that the maximum number of pages assigned to a student is minimum.
Examples:
Input: pages = {8, 15, 10, 20, 8}, M = 2
Output: 31
Explanation: One optimal distribution is [8, 15, 8] and [10, 20]
- The 1st student receives [8, 15, 8] which has a total of 8 + 15 + 8 = 31 pages.
- The 2nd student receives [10, 20] which has a total of 10 + 20 = 30 pages.
- The distribution is max(31, 30) = 31.
It can be shown that there is no distribution with maximum number of pages less than 31.
Input: pages = {6, 1, 3, 2, 2, 4, 1, 2}, M = 3
Output: 7
Explanation: One optimal distribution is [6, 1], [3, 2, 2], and [4, 1, 2]
- The 1st student receives [6, 1] which has a total of 6 + 1 = 7 pages.
- The 2nd student receives [3, 2, 2] which has a total of 3 + 2 + 2 = 7 pages.
- The 3rd student receives [4, 1, 2] which has a total of 4 + 1 + 2 = 7 pages.
- The distribution is max(7, 7, 7) = 7.
It can be shown that there is no distribution maximum number of pages less than 7.
Approach: The problem can be solved based on the concept of backtracking:
For each book there are two choices
- Give a book to student and sum the no of pages for that student
- Skip that student and give the book to another student.
After all books are allocated
- Find the maximum no of pages allocated for a student in every case and
- Store the minimum among the maximum allocation
Follow the given steps to solve the problem using the above approach:
- Recursively for every book:
- Loop through each student and assign the book to him or move on to the next student.
- Once all the books have been distributed,
- Calculate the maximum number of pages assigned to a student and
- Return the minimum of the current maximum, and answer calculated in the earlier steps
Below is the implementation for the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int ans = INT_MAX;vector<int> students;// Function to minimize the maximum number of pagesvoid rec(int i, int N, vector<int>& pages, int M){ if (i == N) { // If all books are included then find // the maximum no of pages for any // student store minimum among // the maximum ans = min(ans, *max_element(students.begin(), students.end())); return; } // ith book can go in any of the students for (int j = 0; j < M; ++j) { // Include the book for jth student students[j] += pages[i]; // Recursively call for the next book rec(i + 1, N, pages, M); // If the ith book is not included for jth student students[j] -= pages[i]; }}// Driver's codeint main(){ vector<int> pages = { 8, 15, 10, 20, 8 }; int M = 2; students.assign(M, 0); // Function call rec(0, pages.size(), pages, M); cout << ans << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { static int ans = Integer.MAX_VALUE; static int[] students = new int[2]; // Function to minimize the maximum number of pages static void rec(int i, int N, int[] pages, int M) { if (i == N) { // If all books are included then find the // maximum no of pages for any student store // minimum among the maximum ans = Math.min( ans, Arrays.stream(students).max().getAsInt()); return; } // ith book can go in any of the students for (int j = 0; j < M; j++) { // Include the book for jth student students[j] += pages[i]; // Recursively call for the next book rec(i + 1, N, pages, M); // If the ith book is not included for jth // student students[j] -= pages[i]; } } public static void main(String[] args) { int[] pages = { 8, 15, 10, 20, 8 }; int M = 2; // Function call rec(0, pages.length, pages, M); System.out.print(ans); }}// This code is contributed by lokesh (lokeshmvs21). |
Python3
# python3 code to implement the above approachimport sysans = 2147483647students = [] # Function to minimize the maximum number of pagesdef rec(i, N, pages, M) : global ans if (i == N) : # If all books are included then find # the maximum no of pages for any # student store minimum among # the maximum ans = min(ans, max(students)) return # ith book can go in any of the students for j in range(0, M) : # Include the book for jth student students[j] += pages[i] # Recursively call for the next book rec(i + 1, N, pages, M) # If the ith book is not included for jth student students[j] -= pages[i] # Driver's codeif __name__ == "__main__": pages = [ 8, 15, 10, 20, 8 ] M = 2 students = [0] * M # Function call rec(0, len(pages), pages, M) print(ans) # This code is contributed by code_hunt. |
C#
// C# program to of the above approachusing System;using System.Linq;class GFG { static int ans = Int32.MaxValue; static int[] students = new int[2]; // Function to minimize the maximum number of pages static void rec(int i, int N, int[] pages, int M) { if (i == N) { // If all books are included then find the // maximum no of pages for any student store // minimum among the maximum ans = Math.Min( ans, students.Max()); return; } // ith book can go in any of the students for (int j = 0; j < M; j++) { // Include the book for jth student students[j] += pages[i]; // Recursively call for the next book rec(i + 1, N, pages, M); // If the ith book is not included for jth // student students[j] -= pages[i]; } } // Driver Code public static void Main() { int[] pages = { 8, 15, 10, 20, 8 }; int M = 2; // Function call rec(0, pages.Length, pages, M); Console.Write(ans); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript program for the above approach let ans = 2147483647; let students = []; // Function to minimize the maximum number of pages const rec = (i, N, pages, M) => { if (i == N) { // If all books are included then find // the maximum no of pages for any // student store minimum among // the maximum ans = Math.min(ans, Math.max(...students)); return; } // ith book can go in any of the students for (let j = 0; j < M; ++j) { // Include the book for jth student students[j] += pages[i]; // Recursively call for the next book rec(i + 1, N, pages, M); // If the ith book is not included for jth student students[j] -= pages[i]; } } // Driver's code let pages = [8, 15, 10, 20, 8]; let M = 2; students = new Array(M).fill(0); // Function call rec(0, pages.length, pages, M); document.write(ans); // This code is contributed by rakeshsahni</script> |
Output
Minimum no of pages: 31
Time Complexity: O(M * MN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
