Lintcode 183. 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.

Challenge

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

Notice

You couldn't cut wood into float length.

If you couldn't get >= k pieces, return 0.

Analysis:
Binary search for the result. The min length is 1, and the max length is the Max(L[i]). So we can try every possible length and calculate how many pieces can we cut? If the number is greater than k, means the the number we tried might be too small. Otherwise, the number is too large. So we can do it via binary search. The total time complexity would be O(nlogAns)

Code (Java):

public 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
     */
    public int woodCut(int[] L, int k) {
        if (L == null || L.length == 0 || k <= 0) {
            return 0;
        }

        int lo = 1;
        int hi = 0;
        for (int i = 0; i < L.length; i++) {
            hi = Math.max(hi, L[i]);
        }

        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            int pieces = getPieces(mid, L);
            if (pieces < k) {
                hi = mid;
            } else {
                lo = mid;
            }
        }

        if (getPieces(hi, L) >= k) {
            return hi;
        } else if (getPieces(lo, L) >= k){
            return lo;
        } else {
            return 0;
        }
    }

    private int getPieces(int len, int[] L) {
        int ans = 0;
        for (int l : L) {
            ans += l / len;
        }

        return ans;
    }
}