[LintCode] Wood Cut

NO IMAGE

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.

Example

For L=[232, 124, 456]

Solution

public class Solution {
public int woodCut(int[] L, int k) {
int n = L.length;
if (n == 0) return 0;
Arrays.sort(L);
int start = 1;
int end = L[n-1];
int res = 0;
while (start <= end) {
int mid = start   (end - start)/2;
int sum = 0;
for (int i = 0; i < n; i  ) {
sum =L[i]/mid;
}
if (sum >= k) {
res = mid;
start = mid   1;
}
else end = mid - 1;
}
return res;
}
}