Problem

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.

 Notice

You couldn't cut wood into float length.

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

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

错误思路

1. 暴力解法:

   1. one for loop to find the wood of min length

   2. len start from min length to cut

       if pieces == k, return len  
       else len--
      

   3. 时间复杂度 O(len * n) : len是木的最短长度, n是木的数量

   4. 错误原因:

      1. 给定数组[1, 10000, 344444, 389544], k = 1, 那么389544便是答案.

正确的暴力解法:

1. find the wood of max length
2. start from that length to cut the wood

优化

• Our purpose is to find the most suitable len to cut.
• When the len decrements from the max one, it is a sorted change by one.
• and we are going to find the first one that makes pieces >= k
• Steps:
  • find the max length of wood
  • binary Search,
    • if the pieces < target, end = mid
    • else return mid
• Time complexity
  • O(n * log len)

    public int woodCut(int[] L, int k) {
        if (L == null || L.length == 0) {
            return 0;
        }

        Arrays.sort(L);
        int n = L.length;

        int start = 1;
        int end = L[n - 1];

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int pieces = 0;
            for (int i = 0; i < n; i++) {
                pieces += L[i] / mid;
            }
            // find the last one that makes pieces >= k
            if (pieces >= k) {
                start = mid;
            } else {
                end = mid;
            }
        }
        int pieces = 0;
        for (int i = 0; i < n; i++) {
            pieces += L[i] / start;
        }
        if (pieces >= k) {
            return start;
        }
        for (int i = 0; i < n; i++) {
            pieces += L[i] / end;
        }
        if (pieces >= k) {
            return end;
        }
        return 0;
    }