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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

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;     } }