Lintcode 437. Copy Books

Given n books and the ith book has A[i] pages. You are given k people to copy the nbooks.

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 ith to jth 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?

Example

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

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

Solution:
Binary search for results. Given a max time T, find out the minimum number of people to finish the job. The number of people > k, means the time T we found was too small, so we should try out a bigger time.

Code (Java):

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

        int sum = 0;
        for (int page : pages) {
            sum += page;
        }

        int lo = sum / k;
        int hi = sum;

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

        if (canFinish(pages, k, lo)) {
            return lo;
        } else if (canFinish(pages, k, hi)){
            return hi;
        } else {
            return 0;
        }
    }

    private boolean canFinish(int[] pages, int k, int maxTime) {
        int count = 1;
        int currTime = 0;

        for (int i = 0; i < pages.length; i++) {
            if (pages[i] > maxTime) {
                return false;
            }

            currTime += pages[i];
            if (currTime > maxTime) {
                count++;
                currTime = pages[i];
            }
        }

        return count <= k;
    }
}