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.

Have you met this question in a real interview? 

Yes

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.

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) {

        // write your code here

        if(L == null || L.length == 0) return 0;

        if(L.length == 1){

            return L[0] / (L[0] / k);

        }

        Arrays.sort(L);

        int start = 1, end = L[L.length - 1];

        int max = 0;

        while(start <= end){

            int mid = (end - start) / 2 + start;

            int count = 0;

            for(int l : L){

                count += (l / mid);

            }

            if(count < k){

                end = mid-1;

            } else{

                start = mid+1;

                max = mid;

            }

        }

        return max;

    }

}