Wood Cut

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.

Note

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.

---------------------------- thinking ---------------------------------------

---------------------------- codes -----------------------------------------
class Solution {
public:
    /**
     *@param L: Given n pieces of wood with length L[i]
     *@param k: An integer
     *return: The maximum length of the small pieces.
     */
    int woodCut(vector<int> L, int k) {
        // write your code here
        if (L.size() == 0) return 0;
        if (L.size() == 1) return (L[0]/k);
        int max = 0;
        for (int i = 0; i < L.size(); i++) {
            if (max < L[i]) {
                max = L[i];
            }
        }
       // max = max/L.size();
        int start = 0;
        int end = max;
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            int cnt = 0;
            if (mid == 0) {
                cnt = INT_MAX;
            } else {
                for (int i = 0; i < L.size(); i++) {
                    cnt += L[i]/mid;
                }
                if (cnt >= k) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < L.size(); i++) {
            cnt += L[i]/end;
        }
        if (cnt >= k) {
            return end;
        } else {
            return start;
        }
    }
};