Lintcode 183 Wood Cut

https://www.lintcode.com/problem/183

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.

The obvious intuition is to try every possible length to cut the wood and see if they meet the requirement, during which we find the max value. So this is similar to search through a number within a range of minLength and maxLength, we can use binary search!

Let’s take a look at the solution

export 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
   */
  woodCut(l, k) {
    if(!l.length) {
      return 0
    }

    let maxLength = -Infinity;
    for(let i = 0; i < l.length; i++) {
      if(l[i] > maxLength) {
        maxLength = l[i]
      }
    }

    const cut = (length) => {
      let result = 0;
      for(let i = 0; i < l.length; i++) {
        result += Math.floor(l[i] / length)
      }
      return result;
    }

    let left = 1;
    let right = maxLength;

    while(left + 1 < right) {
      let mid = Math.floor((left + right) / 2);
      let n = cut(mid)
      if(n >= k) {
        left = mid
      } else {
        right = mid
      }
    }

    if(cut(right) >= k) {
      return right
    } else if(cut(left) >= k) {
      return left
    } else {
      return 0;
    }

  }
}

One thing to note is when we are out of the while loop, we still need to check if left or right meets the requirement, if not we return 0.

The time complexity is O(nLogm + Logn) where n is the number of wood and m is the maximum value of the wood length.

Logn comes from caculating the max value of the wood length
nLogm comes from the binary search where we have to search the range Logm times and each iteration we need to calculate the total pieces of wood we can get which is n. So in total it’s O(nLogm)

Lintcode 183 Wood Cut

Lintcode 183 Wood Cut

Leave a Reply Cancel reply