Wood Cut

https://www.lintcode.com/problem/wood-cut

# Solution

Let nn be the length of L.

Initialize start and end of binary search to be 1 and max(L), respectively. Then do binary search and cut search space in half. Caveat is to choose btw start and end that returns k pieces cut.

Complexity:

  • time: O(nlogn)O(n\log n) (binary search has O(logn)O(\log n) iterations, piece takes )
  • space: O(1)O(1)
def woodCut(self, L, k):
    # helper function, returns # of pieces cut
    def piece(cut_len):
        res = 0
        for l in L:
            res += l//cut_len
        return res

    # edge case: L==[]
    if not L:
        return 0

    # binary search
    start, end = 1, max(L)
    while start+1<end:
        mid = (start+end)//2
        if piece(mid)>=k:
            start = mid
        else:
            end = mid

    # now start+1==end, so choose the one that returns k pieces
    if piece(end) >= k:
        return end
    if piece(start) >= k:
        return start
    return 0
Last Updated: 7/19/2020, 3:45:14 PM