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.

You couldn't cut wood into float length.

Example:

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

Challenge:

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

Solution:

We could start with (start = 0; end = maxLenInL) and check whether mid len could be curt into k pieces or not.

Code:

public int woodCut(int[] L, int k) {
    if (L == null || L.length == 0) {
        return 0;
    }
    int start = 0;
    int end = 0;
    for (int l : L) {
        end = Math.max(l, end);
    }
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (pieces(L, mid) >= k) {
            start = mid;
        } else {
            end = mid;
        }
    }
    return start;
}
private int pieces(int[] L, int len) {
    int k = 0;
    for (int l : L) {
        k += l / len;
    }
    return k;
}