Question

from lintcode
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. )

Idea

At the beginning, I was thinking of exhausting all possibilities, which is separating the array into k partitions.
However, the question asks for the best strategy only. So binary searching the answer also works. So previous thought was dumped.
The question description seems complicated, but in fact, it simply asks for the time spent to finish the copy in the case of best strategy (least time consumption).

Start from 0 to the max integer, perform the binary search. For each midpoint, we assume it the right answer, namely, the guess, i.e. the time spent. We then try to allocate books, ensuring that each person works on the number of pages that is no larger than the guess, and the number of persons allocated does not exceed the given one. If these two conditions cannot be satisfied, we know the guess is too small. Else, we can try an even smaller one.

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.length == 0) return 0;
        
        int min = 0;
        int max = Integer.MAX_VALUE;
        while (min + 1 < max) {
            int guess = min + (max - min) / 2;
            if (valid(pages, k, guess))
              max = guess;
            else
              min = guess;
        }
        
        if (valid(pages, k, max))
          return max;
        return min;
    }
    
    private boolean valid(int[] pages, int k, int guessMaxTime) {
        int numOfPersons = 0;
        int remainTime = 0;
        for(int pageCount : pages) {
            if (pageCount > guessMaxTime)
              return false;
            if (pageCount > remainTime) {
                numOfPersons++;
                remainTime = guessMaxTime;
            }
            remainTime -= pageCount;
        }
        return numOfPersons <= k;
    }
}