Copy Books

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?

java

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 max = Integer.MIN_VALUE, sum = 0; for (int i = 0; i < pages.length; i++) { sum += pages[i]; if (max < pages[i]) { max = pages[i]; } } int start = max, end = sum, mid = 0; while (start + 1 < end) { mid = (end + start) / 2; if (getCount(pages, mid) > k) { start = mid; } else { end = mid; } } if (getCount(pages, start) <= k) { return start; } else { return end; } } private int getCount(int[] pages, int limit) { int copyer = 1, sum = 0; for (int i = 0; i < pages.length; i++) { if (sum + pages[i] > limit) { copyer++; sum = 0; } sum += pages[i]; } return copyer; } }

python

class Solution: """ @param pages: an array of integers @param k: An integer @return: an integer """ def copyBooks(self, pages, k): # write your code here if pages == None or len(pages) == 0: return 0 start, end = max(pages), sum(pages) while start + 1 < end: mid = (start + end) // 2 if self.getCopyer(pages, mid) > k: start = mid else: end = mid if self.getCopyer(pages, start) <= k: return start else: return end def getCopyer(self, pages, limit): copyer, sumVal = 1, 0 for i in pages: if sumVal + i > limit: copyer += 1 sumVal = 0 sumVal += i return copyer