Copy Books – Python 3 ( Week 14 – 08)

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 == []:
            return 0
        
        start, end = max(pages), sum(pages)
        
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self.get_least_people(pages, mid) <= k:
                end = mid
            else:
                start = mid
                
        if self.get_least_people(pages, start) <= k:
            return start
        
        return end
    #log(end - start) * number of book    
    def get_least_people(self, pages, time_limit):
        count = 1
        time_cost = 0
        for page in pages:
            if time_cost + page > time_limit:
                count += 1
                time_cost = page
            else:
                time_cost += page
        return count