Allocate Books

N number of books are given. 
The ith book has Pi number of pages. 
You have to allocate books to M number of students so that maximum number of pages alloted to a student is minimum. A book will be allocated to exactly one student. Each student has to be allocated at least one book. Allotment should be in contiguous order, for example: A student cannot be allocated book 1 and book 3, skipping book 2.

NOTE: Return -1 if a valid assignment is not possible

Input:

List of Books
M number of students
Your function should return an integer corresponding to the minimum number.

Example:

P : [12, 34, 67, 90]
M : 2

Output : 113

There are 2 number of students. Books can be distributed in following fashion : 
  1) [12] and [34, 67, 90]
      Max number of pages is allocated to student 2 with 34 + 67 + 90 = 191 pages
  2) [12, 34] and [67, 90]
      Max number of pages is allocated to student 2 with 67 + 90 = 157 pages 
  3) [12, 34, 67] and [90]
      Max number of pages is allocated to student 1 with 12 + 34 + 67 = 113 pages

Of the 3 cases, Option 3 has the minimum pages = 113.
思路1

DFS with memo

Solution:

Time: O(m * n^2)
Space: O(n^2)

public class Solution {
    public int books(ArrayList<Integer> A, int B) {
        if (A.size() == 0 || B > A.size()) return -1;
        List<Integer> books = new ArrayList<>(A);
        int[][] memo = new int[A.size() + 1][B + 1];
        return partition(books, B, memo);
    }
    
    private int sum(List<Integer> list, int from, int to) {
        int sum = 0;
        for (int i = from; i <= to; i ++) {
            sum += list.get(i);
        }
        return sum;
    }
    
    private int partition(List<Integer> A, int B, int[][] memo) {
        int n = A.size();
        if (memo[n][B] != 0) {
            return memo[n][B];
        }
        if (B == 1) {
            return sum(A, 0, n - 1);
        }
        if (n == 1) {
            return A.get(0);
        }
        int minPage = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i ++) {
            minPage = Math.min(minPage, Math.max(partition(A.subList(0, i), B - 1, memo), sum(A, i, n - 1)));
        }
        memo[n][B] = minPage;
        return minPage;
    }
}

dp:

 
Time: O(m * n^2)
Space: O(n^2)


public class Solution {
    public int books(ArrayList<Integer> A, int B) {
        if (A.size() == 0 || B > A.size()) return -1;
        List<Integer> books = new ArrayList<>(A);
        return partition(books, B);
    }
    
    private int sum(List<Integer> list, int from, int to) {
        int sum = 0;
        for (int i = from; i <= to; i ++) {
            sum += list.get(i);
        }
        return sum;
    }
    
    private int partition(List<Integer> A, int B) {
        int n = A.size();
        int[][] dp = new int[n + 1][B + 1];
        // n = 1
        for (int i = 1; i <= B; i ++) {
            dp[1][i] = A.get(0);
        }
        // B = 1
        for (int i = 1; i <= n; i ++) {
            dp[i][1] = sum(A, 0, i - 1);
        }
        
        for (int i = 2; i <= B; i ++) {
            for (int j = 2; j <= n; j ++) {
                int minPage = Integer.MAX_VALUE;
                for (int p = 1; p <= j; p ++) {
                    minPage = Math.min(minPage, Math.max(dp[p][i - 1], sum(A, p, j - 1)));
                }
                dp[j][i] = minPage;
            }
        }

        return dp[n][B];
    }
}

思路2

We can actually use binary search for this problem. 
The minimum possible number is the max value in the array, in the case when M = size of the array, so every student has one book.
The maximum possible number is the the sum of the array, in the case when M = 1, so the one student read all the books.
If we are given a number of max pages a student reads, we can use it to calculate the number of students needed to finish reading all the books.
if the number of students is > M, then we know our max page is too small, otherwise it's too big.
Again, because left, and right will keep changing until we find the minimum maxBooks, it's guaranteed that the answer is one of the sum of elements in the array.

Solution:

Time: O(nlog(sum(A)))
Space: O(1)

public class Solution {
    public int books(ArrayList<Integer> A, int B) {
        if (A.size() == 0 || B > A.size()) return -1;
        List<Integer> books = new ArrayList<>(A);
        return partition(books, B);
    }
    
    private int max(List<Integer> list) {
        int m = list.get(0);
        for (int i = 1; i < list.size(); i ++) {
            m = Math.max(m, list.get(i));
        }
        return m;
    }
    
    private int sum(List<Integer> list, int from, int to) {
        int sum = 0;
        for (int i = from; i <= to; i ++) {
            sum += list.get(i);
        }
        return sum;
    }
    
    private int numberOfStudents(List<Integer> list, int maxBooks) {
        int num = 1;
        int currBook = 0;
        for (int i = 0; i < list.size(); i ++) {
            currBook += list.get(i);
            if (currBook > maxBooks) {
                num ++;
                currBook = list.get(i);
            }
        }
        return num;
    }
    
    private int partition(List<Integer> A, int B) {
        int n = A.size();
        int left = max(A);
        int right = sum(A, 0, n - 1);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (numberOfStudents(A, mid) <= B) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}