Copy Books 437

Question

Given an array A of integer with size of n( means n books and number of pages of each book) and k people to copy the 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.) Each person have can copy one page per minute. Return the number of smallest minutes need to copy all the books.

Example

Given array A = [3,2,4], k = 2.

Return 5( First person spends 5 minutes to copy book 1 and book 2 and second person spends 4 minutes to copy book 3. )

Challenge

Could you do this in O(n*k) time ?

Solution

这道题有两种解法。第一种是基本的DP，第二种是用二分法搜索可能最小时间。

第一种DP建立一个二维数组(n+1 * k+1)，T[i][j]表示前i本书分配给j个人copy。

  1. 初始化T[1][j]=pages[0]，初始化T[i][1]= pages[0] + pages[1] + ... + pages[i-1]

  2. 然后从2本书开始到n本书为止，依次计算分配给2～k个人的最小时间。当人数比书大时，有些人不干活也不会影响速度，因此和少一个人情况相同。

  3. 对于新加进来的人j，考虑让前j－1个人copy的书的数量h（0～n），则新进来的人相应的copy的数量为n～0本，前者的时间为T[h][j-1]，后者的时间为T[i][1]-T[h][1]（即一个人copy从h＋1到i本需要的时间），两者的较大值即为T[i][j]的一个后选项。选择所有后选项中的最小值即为T[i][j]的值。这里可以优化，即我们知道如果前j－1个人copy的书的数量少于j－1必然有人不干活，而所有人都干活的结果一定会更快，所以h的范围可以从j－1～n，因为我们知道h为0～j－1时的结果一定不会是最优的答案。

第二种方法很巧妙地用到了二分搜索的方法。我们要找的最优解是某一个时间的临界点，当时间小于这个值时，k个人一定不可能完成任务，当时间大于等于这个值时，则可以完成。

  1. 首先将时间的范围设为所有整数（0～99999999）。计算中点作为这次的假设时间临界点，尽量让每个人的工作时间都接近这个临界点。

  2. 假设当前某个人之前分配的书的页数加上当前书的页数小于当前临界点，则直接把这本书分配给这个人而不会影响最优解；

  3. 若大于，则看当前书的页数是否大于临界点： 1）若大于，则说明当前的临界值太小，连这本书都不能copy完全，所以最优解一定大于当前临界点，因此要增大临界点再重复2 2）若小于，则将书分配给下一个人copy

  4. 若所有书分配完时，所需要的人数比k小（即还剩下人没用），则说明每个人干活的时间太多，最优时间一定比当前值小，反之则说明每个人干活的时间太少，最优时间比当前值大

  5. 考虑3-4中的所有情况，若最优解比当前临界点小，则向当前临界点左半边搜索，否则向当前临界点右半边搜索，直到左右边界重合，此时的临界点（即左右边界）即为最优解。

代码如下：

DP

public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        // write your code here
        // if(pages == null || pages.length == 0){
        //     return 0;
        // }

        // if(k < 1){
        //     return -1;
        // }

        // int n = pages.length;
        // int[][] T = new int[n + 1][k + 1];

        // for(int j = 1; j <= k; j++){
        //     T[1][j] = pages[0];
        // }

        // int sum = 0;
        // for(int i = 1; i <= n; i++){
        //     sum += pages[i - 1];
        //     T[i][1] = sum;
        // }

        // for(int i = 2; i <= n; i++){
        //     for(int j = 2; j <= k; j++){
        //         if(j > i){
        //             T[i][j] = T[i][j - 1];
        //             continue;
        //         }
        //         int min = Integer.MAX_VALUE;
        //         for(int h = j - 1; h <= i; h++){
        //             int temp = Math.max(T[h][j - 1], T[i][1] - T[h][1]);
        //             min = Math.min(min, temp);
        //         }
        //         T[i][j] = min;
        //     }
        // }

        // return T[n][k];
    }
}

Binary search

public class Solution {
    /**
     * @param pages: an array of integers
     * @param k: an integer
     * @return: an integer
     */
    public int copyBooks(int[] pages, int k) {
        // write your code here
        //O(n*logM)? O(n*k)
        int l = 0;
        int r = 9999999;
        while( l <= r){
            int mid = l + (r - l) / 2;
            if(search(mid,pages,k))
                r = mid-1;
            else
                l = mid+1;
        }
        return l;
    }

    private boolean search(int total, int[] page, int k){
    //至少有一个人copy，所以count从1开始
        int count = 1;
        int sum = 0;
        for(int i = 0; i < page.length;) {
            if(sum + page[i] <= total){
                sum += page[i++];
            }else if(page[i] <= total){
                sum = 0;
                count++;
            }else{
                return false;
            }
        }

        return count <= k;
    }
}

results matching ""

    No results matching ""