Wood Cut

Question

Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.

Example For L=[232, 124, 456], k=7, return 114.

Thoughts

对从0到最大length的数，mid计算count

小于k,就取左半边 大于k,就取右半边

Solution

class Solution:
    """
    @param L: Given n pieces of wood with length L[i]
    @param k: An integer
    return: The maximum length of the small pieces.
    """
    def woodCut(self, L, k):
        # write your code here
        if not L:
            return 0
        start = 0
        end = max(L)
        while start + 1 < end:
            mid = start + (end-start) / 2
            count = self.getCount(L, mid)
            if count < k:
                end = mid - 1
            elif count >= k:
                start = mid

        startCount = self.getCount(L, start)
        endCount = self.getCount(L, end)
        if endCount >= k:
            return end
        else:
            return start


    def getCount(self, L, length):
        count = 0
        if length == 0:
            return sys.maxint
        for l in L:
            count += (l/length)
        return count