[LintCode] 437 Copy Books 解题报告

Description
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. )


思路

用二分法来做。二分可能的答案。每次判断什么呢？判断k个人能不能在这个时间里搞定。people()这个函数用来统计给定一个时间minTime需要多少人可以在这个时间内搞定抄那么多书。如果>k，说明这个时间k个人搞不定，时间要再久一点才可以。如果<k，说明不到k个人就能在这个时间内搞定，我们可以试试更少一点的时间。

Code

public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    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 i = 0; i < pages.length; i++) {
            end += pages[i];
            start = Math.max(start, pages[i]);
        }
        
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (people(pages, mid) > k) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        
        if (people(pages, start) <= k) {
            return start;
        }
        return end;
        
    }
    
    public int people(int[] pages, int minTime) {
        if (pages.length == 0) {
            return 0;
        }
        
        int sum = 0;
        int people = 1;
        for (int i = 0; i < pages.length; i++) {
            if (sum + pages[i] > minTime) {
                people++;
                sum = 0;
            }
            sum += pages[i];
        }
        
        return people;
    }
}