Copy Books

Description

Given n books and the i th book hasA[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 i th to j th 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.

Return5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )

Implementation

Link: http://lintcode.com/en/problem/copy-books/

class Solution {  
public:  
    /** 
     * @param pages: a vector of integers 
     * @param k: an integer 
     * @return: an integer 
     */  
    int copyBooks(vector<int> &pages, int k) {  
        // write your code here  
        if(pages.size() == 0) return 0;

        int max = 0;
        int sum = 0;
        for(int i = 0; i < pages.size(); i++) {
            if(max < pages[i]) {
                max = pages[i];
            }
            sum += pages[i];
        }

        int start = max, end = sum;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if(check(mid, pages) > k) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if(check(start, pages) <= k) {
            return start;
        } 
        if(check(end, pages) <= k) {
            return end;
        }
        return 0;
    }  

    int check(int size, vector<int>& pages) {
        // Note: cnt starts with 1
        int cnt = 1;  
        int sum = 0;

        for(int i = 0; i < pages.size(); i++) {
            if(sum + pages[i] <= size) {
                sum += pages[i];
            } else {
                sum = pages[i];
                cnt++;
            }
        }
        return cnt;  
    }  
};