Lintcode 438. Copy Books II

Given n books( the page number of each book is the same) and an array of integer with size k means k people to copy the book and the i th integer is the time i th person to copy one book). You must distribute the continuous id books to one people to copy. (You can give book A[1],A[2] to one people, but you cannot give book A[1], A[3] to one people, because book A[1] and A[3] is not continuous.) Return the number of smallest minutes need to copy all the books.

Example

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

Return 4( First person spends 3 minutes to copy book 1, Second person spends 4 minutes to copy book 2 and 3, Third person spends 4 minutes to copy book 4. )

Code (Java):

public class Solution {
    /**
     * @param n: An integer
     * @param times: an array of integers
     * @return: an integer
     */
    public int copyBooksII(int n, int[] times) {
        if (n <= 0 || times == null || times.length == 0) {
            return 0;
        }
        
        int min = times[0];
        int max = times[0];
        
        for (int i = 0; i < times.length; i++) {
            min = Math.min(min, times[i]);
            max = Math.max(max, times[i]);
        }
        
        int lo = min;
        int hi = min * n;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (canFinish(n, times, mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        
        if (canFinish(n, times, lo)) {
            return lo;
        } else if (canFinish(n, times, hi)) {
            return hi;
        } else {
            return 0;
        }
    }
    
    private boolean canFinish(int n, int[] times, int totalTime) {
        int count = 0;
        for (int time : times) {
            count += totalTime / time;
        }
        
        return count >= n;
    }
}