Wood Cut

Source

• lintcode: Wood Cut

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.

Note
You couldn't cut wood into float length.

Challenge
O(n log Len), where Len is the longest length of the wood.

Python

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 L is None or len(L)==0:
            return 0

        left = 1
        right = max(L)
        result=0

        while left<=right:
            mid = (left+right)/2

            if self.numPieces(mid, L)<k:
                right=mid-1
            else:
                result = mid
                left = mid+1
        return result 

    def numPieces(self, len, L):
        res=0;
        for l in L:
            res+= l/len
        return res