Copy Book

Given n books and the ith book has A[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 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. )

Challenge:

O(n log limit), where limit is the maximum number of pages need to be copy by one copier.

Solution:

Similar to Wood Cut, we could start with (start = max pages; end = total pages) and check whether mid number could be finished by k copier or not.

Code:

public int copyBooks(int[] pages, int k) {
    // write your code here
    if (pages == null || pages.length == 0) {
        return 0;
    }
    int start = 0;
    int end = 0;
    for (int p : pages) {
        end += p;
        start = Math.max(start, p);
    }
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (numOfCopier(pages, mid) > k) {
            start = mid;
        } else {
            end = mid;
        }
    }
    if (numOfCopier(pages, start) <= k) {
        return start;
    }
    return end;
}

private int numOfCopier(int[] pages, int limit) {
    int person = 1;
    int sum = pages[0];
    for (int i = 1; i < pages.length; i++) {
        if (sum + pages[i] > limit) {
            person++;
            sum = 0;
        }
        sum += pages[i];
    }
    return person;
}