美文网首页
Copy Books II - non-optimized ve

Copy Books II - non-optimized ve

作者: Star_C | 来源:发表于2018-04-09 00:04 被阅读0次

Question

from lintcode
Given n books( the page number of each book is the same) and an array of integer with size k means k people to copy the book and the i th integer is the time i th person to copy one book). You must distribute the continuous id books to one people to copy. (You can give book A[1],A[2] to one people, but you cannot give book A[1], A[3] to one people, because book A[1] and A[3] is not continuous.) Return the number of smallest minutes need to copy all the books.
Example
Given n = 4, array A = [3,2,4], .

Return 4( First person spends 3 minutes to copy book 1, Second person spends 4 minutes to copy book 2 and 3, Third person spends 4 minutes to copy book 4. )

Idea

You can give arbitrary books to current person, and give the remained ones to next person... Try all possibilities by DFS search. Remember to cache some calculated results.

Note: This solution can only pass 65% of the test cases. I will update a better one later.

``java
/**

  • f(i, remain)

  • f represents the minimum time required to finish the remained books when starting from i-indexed person
    /
    public class Solution {
    /
    *

    • @param n: An integer

    • @param times: an array of integers

    • @return: an integer
      */
      public int copyBooksII(int numOfBooks, int[] times) {

      if (times.length == 0) return Integer.MAX_VALUE;
      if (numOfBooks == 0) return 0;

      this.times = times;
      this.computed = new int[times.length + 1][numOfBooks + 1];
      for (int i = 0; i < computed.length; i++)
      for (int j = 0; j < computed[0].length; j++)
      computed[i][j] = -1;
      return compute(0, numOfBooks);
      }

    private int[] times;

    private int[][] computed;

    private int compute(int i, int remainBooks) {
    if (i == times.length)
    return Integer.MAX_VALUE;
    if (this.computed[i][remainBooks] > 0)
    return this.computed[i][remainBooks];

    int minTime = Integer.MAX_VALUE;
    /**
     *  try each possible paths
     */
    for(int books = 0; books <= remainBooks; books++) {
        int consume = books * this.times[i];
        int minConsumeOfPath;
        if (books == remainBooks) {
            minConsumeOfPath = consume;
        } else {
            /**
             *  why Math.max?
             *  The shortest time was bounded by the person who consumes the most time
             */
            minConsumeOfPath = Math.max(consume, compute(i + 1, remainBooks - books));
        }
        minTime = Math.min(minTime, minConsumeOfPath);
    }
    
    this.computed[i][remainBooks] = minTime;
    return minTime;
    

    }
    }

相关文章

网友评论

      本文标题:Copy Books II - non-optimized ve

      本文链接:https://www.haomeiwen.com/subject/lrsvhftx.html