Given_n_books and the_i_th book hasA[i]pages. You are given_k_people to copy the_n_books.

_n_books list in a row and each person can claim a continous range of the_n_books. For example one copier can copy the books from_i_th to_j_th continously, but he can not copy the 1st book, 2nd book and 4th book (without 3rd book).

They start copying books at the same time and they all cost 1 minute to copy 1 page of a book. What's the best strategy to assign books so that the slowest copier can finish at earliest time?

Have you met this question in a real interview?

Yes

Example

Given array A =[3,2,4], k =2.

Return5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )

public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        // write your code here
        if (pages == null || pages.length == 0) {
            return 0;
        }

        int start = 1;
        int end = pages[0];
        for(int i = 1; i < pages.length; i++) {
            end = end + pages[i];
        }

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (!canFinish(pages, k, mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (start < end && canFinish(pages, k, start)) {
            return start;
        }
        return end;
    }


    public boolean canFinish(int[] pages, int k, int time) {
        int timeLeft = time;
        int slowest = Integer.MIN_VALUE;
        k = k - 1;
        for (int i = 0; i < pages.length; i++) {
            slowest = Math.max(slowest, pages[i]);
            if (timeLeft >= pages[i]) {
                timeLeft = timeLeft - pages[i];
            } else if (timeLeft < pages[i] && k > 0) {
                k = k - 1;
                timeLeft = time - pages[i];
            } else if (timeLeft < pages[i] && k <= 0) {
                return false;
            }
        }
        if (time < slowest) {
            return false;
        }
        return true;
    }
}

1. dynamic programming

f[i][j] 是前i个人抄前j本书的最短时间

f[i][j] = min{ max{f[i - 1][k], A[k]....A[j - 1]), k->{0, j} }

f[0][j] 前0个人抄前j本书 应该是最大值

f[i][0] 前i个人抄前0本书 应该是0

public class Solution {
    /*
     * @param pages: an array of integers
     * @param k: An integer
     * @return: an integer
     */

    //f[i][j] 是前i个个抄前j本书所用的最短时间

    public int copyBooks(int[] pages, int k) {
        // write your code here
        if (pages == null || pages.length == 0) {
            return 0;
        }
        int[] sum = new int[pages.length + 1];
        sum[0] = 0;

        for (int i = 1; i <= pages.length; i++) {
            sum[i] += sum[i - 1] + pages[i - 1];
        }

        int[][] f = new int[k + 1][pages.length + 1];
        //initialization
        for (int i = 0; i <= k; i++) {
            f[i][0] = 0;
        }

        for (int j = 1; j <= pages.length; j++) {
            f[0][j] = Integer.MAX_VALUE;
        }



        for (int i = 1; i <= k; i++) {
            for (int j = 1; j <= pages.length; j++) {
                f[i][j] = Integer.MAX_VALUE;
                for (int q = 0; q <= j; q++) {
                    int remains = 0;
                    if (q == 0) {
                        remains = sum[j - 1];
                    } else {
                        remains = sum[j - 1] - sum[q - 1];
                    }
                    f[i][j] = Math.min(f[i][j], Math.max(f[i][q], remains));
                }
            }
        }

        return f[k][pages.length];
    }
}