Posts Allocate Minimum Pages (geeksforgeeks - SDE Sheet)
Post
Cancel

Allocate Minimum Pages (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

You have n books, each with arr[i] a number of pages. m students need to be allocated contiguous books, with each student getting at least one book. Out of all the permutations, the goal is to find the permutation where the sum of the maximum number of pages in a book allotted to a student should be the minimum, out of all possible permutations.

Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see the explanation for better understanding).

geeksforgeeks

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {

    // Function to find minimum number of pages.
    public static long findPages(int n, int[] arr, int m) {

        long l = 1; // read min 1 page
        long r = sum(arr, n); // read max all pages by single student

        // each student need to read at least 1 book
        // if there are less books than students, return -1
        if(n < m)
            return -1;

        // init: not possible
        long minBooks = -1;

        while(l<=r){

            // number of pages allowed at max per student
            long pages = l + (r - l) / 2;

            // check if those number of pages is a possible solution
            if(check(arr, n, m, pages)){
                // update new min value possible and check for lower value
                minBooks = pages;
                r = pages - 1;
            // otherwise, try with more number of pages
            }else{
                l = pages + 1;
            }

        }

        return minBooks ;

    }

    // check if we allow any student to read at max x number of pages, we would be able to cover all students
    public static boolean check(int[] arr, int n, int students, long pagesAllowed){

        // pages read by the current student
        long currentPages = 0;

        // number of student needed to read all
        int studentsNeeded = 1;

        // traverse all books
        for(int i=0; i<n; i++){

            // if current book has more pages than allowed, we can directly return false
            if(arr[i] > pagesAllowed)
                return false;

            // if the current student can read the current book
            // add to the number of pages read and move forward
            if(currentPages + arr[i] <= pagesAllowed){
                currentPages += arr[i];

            // otherwise, we need another student to cover this book
            }else{
                currentPages = arr[i];
                studentsNeeded++;
            }

        }

        //check if we have enough students to cover all the books
        return studentsNeeded <= students;
    }

    public static long sum(int[] arr, int n){
        long s = 0;
        for(int i=0; i<n; i++)
            s += arr[i];
        return s;
    }

};
This post is licensed under CC BY 4.0 by the author.