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.

Notice

You couldn't cut wood into float length.

Example

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

Analyse:

Runtime: Time exceeded.

 1 class Solution {
 2 public:
 3     /** 
 4      *@param L: Given n pieces of wood with length L[i]
 5      *@param k: An integer
 6      *return: The maximum length of the small pieces.
 7      */
 8     int woodCut(vector<int> L, int k) {
 9         // write your code here
10         if (L.empty()) return 0;
11         // first sort the array
12         sort(L.begin(), L.end());
13         // fix the first number x, calculate the times of other numbers to x and sum them to check if exceed k.
14         // If exceeded, use binary divide to narrow the value of x
15         // If not exceeded, save and update result.
16         int result = 0;
17         for (int i = 0; i < L.size(); i++) {
18             // first check if L[i] is the longest length
19             // say if the sum of times of each number <= k, then we need to more devide L[i]; otherwise, let it continue
20             int tempCount = 0;
21             for (int j = 0; j < L.size(); j++)
22                 tempCount += L[j] / L[i];
23             if (tempCount >= k) {
24                 result = max(result, L[i]);
25                 continue;
26             }
27             else {
28                 int low = 1, high = L[i];
29                 while (low <= high) {
30                     int tempPieces = 0, mid = low + (high - low) / 2;
31                     for (int j = 0; j < L.size(); j++)
32                         tempPieces += L[j] / mid;
33                     if (tempPieces >= k) {
34                         result = max(result, mid);
35                         low = mid + 1;
36                     }
37                     else high = mid - 1;
38                 }
39                 result = max(result, high);
40                 return result;
41             }
42         }
43         return result;
44     }
45 };

View Code

Analyse: Find the longest wood and use binary search to find a right one.

 1 class Solution {
 2 public:
 3     /** 
 4      *@param L: Given n pieces of wood with length L[i]
 5      *@param k: An integer
 6      *return: The maximum length of the small pieces.
 7      */
 8     int woodCut(vector<int> L, int k) {
 9         // write your code here
10         if (L.empty()) return 0;
11         
12         // find max, use binary search to scan possible values between 1 and max
13         sort(L.begin(), L.end());
14         int low = 1, high = L[L.size() - 1], result = 0;
15         while (low <= high) {
16             int mid = low + (high - low) / 2, tempPieces = 0;
17             for (int number : L) 
18                 tempPieces += number / mid;
19             if (tempPieces >= k) {
20                 result = max(result, mid);
21                 low = mid + 1;
22             }
23             else high = mid - 1;
24         }
25         return result;
26     }
27 };