Massive Algorithms: LintCode 437

LintCode 437 - Copy Books

Also check LeetCode 410 - Split Array Largest Sum
http://massivealgorithms.blogspot.com/2015/11/leetcode2.html
http://www.lintcode.com/en/problem/copy-books/
http://massivealgorithms.blogspot.com/2015/10/find-minimum-time-to-finish-all-jobs.html
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

O(n^2 * k) solution

X. O(n * k) solution

https://www.bbsmax.com/A/VGzlWpqYdb/

dp[c][i-1] is mono-inc by c, cur is mono-dec. min(.., max(cur,last)) is V-like in 2D plane. So we can use 2-pointers to find the bottom of the V!

https://chenlp.wordpress.com/2015/08/08/copy-books-lintcode/

dynamical programming; dp[ia][ib] represents the smallest minutes needed for ia people to copy ib books. Initially dp[ia][ib] = min(dp[ia][ib], max(dp[ia-1][ic], sum(pages[ic], …, pages[ib])) ) for ia <= ic <= ib-1.

To optimize it, firstly we can calculate the partial sum of pages, so that it is easier to calculate sum(pages[ic], …, pages[ib]).

Secondly, note that we get the smallest time for dp[ia][ib] when dp[ia-1][ic] is closest to sum(pages[ic], …, pages[ib]). And when ic is increasing, dp[ia-1][ic] is increasing and sum(pages[ic], …, pages[ib]) is decreasing. So ic only need to start from the point K which makes

sum(pages[ic], …, pages[ib])>dp[ia-1][ic]

to the point which makes

sum(pages[ic], …, pages[ib])<=dp[ia-1][ic].

The point K can be got from the end point of the previous step to get dp[ia][ib-1];

Here is the code with time complexity O(n*k):

int copyBooks(vector<int> &pages, int k) {
// write your code here
int N = pages.size();
if(N==0 || k<=0) return 0;
k = min(k, N);
vector<vector<int>> dp(k, vector<int>(N,INT_MAX));
partial_sum(pages.begin(), pages.end(), dp[0].begin());
for(int ia=1; ia<k; ++ia){
dp[ia][ia] = max(pages[ia], dp[ia-1][ia-1]);
int left = ia, right = ia+1;
while(right<N){
int crt = dp[0][right] - dp[0][left];
dp[ia][right] = min(dp[ia][right], max(dp[ia-1][left], crt));
if(left<right && crt>dp[ia-1][left]){
++left;
} else {
++right;
if(left>ia) --left;
}
}
}
return dp[k-1][N-1];
}

Similar DP idea with some optimization.

Optimization:
Use two pointers left and right to calculate minutes[i][right].
We move left of right according to the monotonicity of minutes[i][j].

Move left if minutes[i - 1][left] > sum(left + 1, right), or left == right
Move right otherwise. Also move left back by 1 step in this case, since it would be a potential solution.

    int copyBooks(vector<int> &pages, int k) {
        int n = pages.size();
        k = min(n, k);
        vector<int> sum_from_start(n, 0);
        partial_sum(pages.begin(), pages.end(), sum_from_start.begin());
        vector<vector<int> > minutes(k + 1, vector<int>(n, INT_MAX));
        for (int j = 0; j < n; j++) {
            minutes[1][j] = sum_from_start[j];
        }
        for (int i = 2; i <= k; i++) {
            minutes[i][0] = sum_from_start[1];
            int left = 0, right = 1;
            while (right < n) {
                int curr = sum_from_start[right] - sum_from_start[left];
                minutes[i][right] = min(max(curr, minutes[i - 1][left]), minutes[i][right]);
                if (left < right && minutes[i - 1][left] < curr) {
                    left++;
                }
                else {
                    right++;
                    // note: we should calculate the next solution starting from left - 1
                    if (left > 0) {
                        left--;
                    }
                }
            }
        }
        return minutes[k][n - 1];
    }

https://chenlp.wordpress.com/2015/08/08/copy-books-lintcode/

To optimize it, firstly we can calculate the partial sum of pages, so that it is easier to calculate sum(pages[ic], …, pages[ib]).

sum(pages[ic], …, pages[ib])>dp[ia-1][ic]

to the point which makes

sum(pages[ic], …, pages[ib])<=dp[ia-1][ic].

The point K can be got from the end point of the previous step to get dp[ia][ib-1];

这个题的状态f[i][j]表示前i个人copy前j本书的最长时间

递推公式的理解为：
f[i][j] = min(f[i][j], max(f[i-1][k], w[k+1][j]))
枚举一个k，由前i-1个人，copy前k本书，那么k+1~j这些书就由第i个人来copy, 这种方案下的最大值如果比f[i][j]小，则更新。
最后答案就是f[k][n]。

本题的切入点是每个人都是连续的copy一段，类似于一段数的切分方案

http://jane4532.blogspot.com/2015/07/lintcode-copy-books.html
https://github.com/awangdev/LintCode/blob/master/Java/Copy%20Books.java
http://jane4532.blogspot.com/2015/07/lintcode-copy-books.html

#### Partition DP
- 第一步, 理解题目要求的问题: 前k个人copy完n本书, 找到最少的用时; 也可以翻译成: `n本书, 让k个人来copy, 也就是分割成k段`.
- 最后需要求出 dp[n][k]. 开: int[n+1][k+1]. 
- 原理:
- 1. 考虑最后一步: 在[0 ~ n - 1]本书里, 最后一个人可以选择copy 1 本, 2 本....n本, 每一种切割的方法的结果都不一样
- 2. 讨论第k个人的情况, 在 j = [0 ~ i] 循环. 而循环j时候最慢的情况决定 第k个人的结果(木桶原理): `Math.max(dp[j][k - 1], sum)`. 
- 3. 其中: `dp[j][k-1]` 是 [k-1]个人读完j本书的结果, 也就是著名的`上一步`. 这里循环考虑的是第k个人不同的j种上一步 : )
- 4. 循环的结果, 是要存在 dp[i][k] = Math.min(Math.max(dp[j][k - 1], sum[j, i]), loop over i, k, j = [i ~ 0])
- Time: O(kn^2), space O(nk)

##### Init
- Init: dp[0][0] = 0, 0个人0本书
- Integer.MAX_VALUE的运用:
- 当 i = 1, k = 1, 表达式: dp[i][k] = Math.min(dp[i][k], Math.max(dp[j][k - 1], sum));
- 唯一可行的情况就只有一种: i=0, k=0, 刚好 0 个人 copy 0 本书, dp[0][0] = 0.
- 其他情况, i = 1, k = 0, 0 个人读 1本书, 不可能发生: 所以用Integer.MAX_VALUE来冲破 Math.max, 维持荒谬值.
- 当 i=0, k=0 的情况被讨论时候, 上面的方程式才会按照实际情况计算出 dp[i][k]
- 这道题的init是非常重要而tricky的

##### 计算顺序
- k个人, 需要一个for loop; 
- k个人, 从copy1本书开始, 2, 3, ... n-1,所以 i=[1, n], 需要第二个for loop
- 在每一个i上, 切割的方式可以有[0 ~ i] 中, 我们要计算每一种的worst time

##### 滚动数组
- [k] 只有和 [k - 1] 相关
- Space: O(n)

The order of people and books doesn't matter

    public int copyBooks(int[] pages, int K) {
        if (pages == null || pages.length == 0) {
            return 0;
        }

        int n = pages.length;
        if (K > n) {
            K = n;
        }
        int[][] dp = new int[n + 1][K + 1];

        //dp[0][0~n] = Integer.MAX_VALUE; // 0 people read n books
        dp[0][0] = 0; // 0 people read 0 book
        for (int i = 1; i <= n; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        
        for (int i = 1; i <= n; i++) {// read i books
            for (int k = 1; k <= K; k++) { // k people
                int sum = 0;
                dp[i][k] = Integer.MAX_VALUE;
                for (int j = i; j >= 0; j--) { // last person k read from [j ~ i] which uses 'sum' time
                    dp[i][k] = Math.min(dp[i][k], Math.max(dp[j][k - 1], sum));
                    if (j > 0) {
                        sum += pages[j - 1];
                    }
                }
            }
        }

        return dp[n][K];
    }

// Rolling array
    public int copyBooks(int[] pages, int K) {
        if (pages == null || pages.length == 0) {
            return 0;
        }

        int n = pages.length;
        if (K > n) {
            K = n;
        }
        int[][] dp = new int[2][n + 1];

        //dp[0][0~n] = Integer.MAX_VALUE; // 0 people read n books
        dp[0][0] = 0; // 0 people read 0 book
        for (int i = 1; i <= n; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        
        for (int k = 1; k <= K; k++) { // k people
            for (int i = 1; i <= n; i++) {// read i books
                int sum = 0;
                dp[k % 2][i] = Integer.MAX_VALUE;
                for (int j = i; j >= 0; j--) { // person k read from j -> i
                    dp[k % 2][i] = Math.min(dp[k % 2][i], Math.max(dp[(k - 1) % 2][j], sum));
                    if (j > 0) {
                        sum += pages[j - 1];
                    }
                }
            }
        }

        return dp[K % 2][n];
    }

http://www.voidcn.com/blog/martin_liang/article/p-5763523.html

int copyBooks(vector<int> &pages, int k) {
    // write your code here
    if (pages.size() == 0 || k == 0)
        return 0;
        
    if (k > pages.size())
        k = pages.size();
    
    vector<vector<int>> dp(k, vector<int>(pages.size()));
    vector<int> auxPages(pages.size());

    auxPages[0] = pages[0]; //页面的累加和
    dp[0][0] = pages[0];
    for (int i=1; i<pages.size(); i++)
    {
        auxPages[i] = auxPages[i-1]+pages[i];
        dp[0][i] = auxPages[i];
    }
    
    //dp[i][j] i个人抄写书，抄到以j下标结尾的书时的最少耗时
    
    for (int i=1; i<k; i++)
    {
        for (int j=i; j<pages.size(); j++)
        {
            int targetValue = INT_MAX;
            for (int m=i; m<=j; m++)
            {
                //i-1人抄到下标为m-1的书，剩下的一人抄从m到j的书
                targetValue = min(max(dp[i-1][m-1], auxPages[j]-auxPages[m-1]), targetValue);
            }
            dp[i][j] = targetValue;
        }
    }
    
    return dp[k-1][pages.size()-1];
}

http://jane4532.blogspot.com/2015/07/lintcode-copy-books.html

dp[i][j] 代表前i本书由j个工作者完成需要的最小时间。状态转移方程如下：

dp[i+1][j+1] = Min(Max(dp[i][k], A[k]+...+A[j+1])), where k from i to j+1

意思就是每加入一个新worker的时候，从后往前累加他需要copy的book，每次更新总体所需要的时间；而总体需要的时间是之前所有worker分配方案中的最优时间和新worker所需时间两者中的较大值。

public int copyBooks(int[] pages, int k) {

// write your code here

int[][] dp = new int[k+1][pages.length+1];

int sum = 0;

int max = 0;

for(int i=1; i<=pages.length; i++){

sum += pages[i-1];

dp[1][i] = sum;

max = Math.max(max, pages[i-1]);

}

if(k>=pages.length){

return max;

}

for(int i=2; i<=k; i++){

for(int j=pages.length-1; j>=i-1; j--){

int current = pages[j];

int min = Math.max(pages[j], dp[i-1][j]);

dp[i][j+1] = min;

for(int l=j-1; l>=i-1; l--){

current += pages[l];

int curMin = Math.max(current, dp[i-1][l]);

if(curMin<min){

dp[i][j+1] = curMin;

min = curMin;

}

return dp[k][pages.length];

}


	public int copyBooks(int[] pages, int k) {
	// write your code here
	int len = pages.length;
	int[][] dp = new int[k+1][len];//dp[i][j] 代表前i本书由j个工作者完成需要的最小时间
	for (int i = 0; i <= k; i ++) {
	for (int j = 0; j < len; j ++) dp[i][j] = Integer.MAX_VALUE;
	}
	k = Math.min(len, k);
	for (int i = 1; i < len; i ++) {
	pages[i] += pages[i - 1];
	}
	for (int i = 1; i <= k; i ++) {
	for (int j = 0; j < len; j ++) {
	if (i == 1 \|\| j == 0) {
	dp[i][j] = pages[j];
	} else {
	for (int r = j - 1; r >= 0; r --) {
	int cur = Math.max(dp[i - 1][r], pages[j] - pages[r]);
	dp[i][j] = Math.min(dp[i][j], cur);
	}
	}
	}
	}
	return dp[k][len - 1];
	}

minutes[i][j] = min( max( minutes[i-1][t], sum(t+1, j) ), where 1 <= i <= k, 0 <= j <= n - 1, 0 <= t < j

    int copyBooks(vector<int> &pages, int k) {
        int n = pages.size();
        k = min(n, k); // don't need more than n people
        vector<int> sum_from_start(n, 0);
        partial_sum(pages.begin(), pages.end(), sum_from_start.begin());
        vector<vector<int> > minutes(k + 1, vector<int>(n, INT_MAX));
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 1 || j == 0) {
                    minutes[i][j] = sum_from_start[j];
                }
                else {
                    for (int t = j - 1; t >= 0; t--) {
                        int curr = max(minutes[i - 1][t], sum_from_start[j] - sum_from_start[t]);
                        minutes[i][j] = min(curr, minutes[i][j]);
                    }
                }
            }
        }
        return minutes[k][n - 1];
    }

http://www.jiuzhang.com/solutions/copy-books/

    public int copyBooks(int[] pages, int k) {
        // write your code here
        if(pages == null){
            return 0;
        }
        int n = pages.length;
        if (n == 0){
            return 0;
        }
           
        if (k > n) {
            k = n;
        }
        int[] sum = new int[n];
        sum[0] = pages[0];
        for (int i = 1; i < n; ++i) {
            sum[i] = sum[i-1] + pages[i];
        }
        int[][] f = new int[n][k];
        for (int i=0; i<n; ++i) f[i][0] = sum[i];
        for (int j=1; j<k; ++j) {
            int p = 0;
            f[0][j] = pages[0];
            for (int i = 1; i < j; ++i) f[i][j] = Math.max(f[i-1][j], pages[i]); 
            for (int i = j; i < n; ++i) {
                while (p < i && f[p][j-1] < sum[i] - sum[p]) ++p;
                f[i][j] = Math.max(f[p][j - 1], sum[i] - sum[p]);                
                if (p > 0) {
                    --p;
                }
                f[i][j] = Math.min(f[i][j], Math.max(f[p][j - 1], sum[i] - sum[p]));         
            }
        }
        return f[n - 1][k - 1];
    }

    int [][]init(int []A)  
    {  
        int n = A.length;
        int [][]w = new int [n+2][n+2];
        for(int i = 1; i <= n; i++) {  
            for(int j = i+1; j <= n; j++)  
            {  
                for(int k = i;k <= j;++k) {
                    w[i][j] += A[k - 1];  
                }
            } 
        }
        return w; 
    } 
    
    public int copyBooks(int[] pages, int k) {
        int n = pages.length;
        int [][]w = init(pages);
        int [][]dp = new int[n + 2][k + 2];
        int [][]s = new int[n + 2][k + 2];
        
        int ans = Integer.MIN_VALUE;
        if(n <= k) {
            for(int i = 0; i < n; i++) 
             ans = Math.max(ans, pages[i]);
            return ans;
        }
        
        for(int i = 0;i <= n;++i)  {
            dp[i][1] = w[1][i];
            
        }
        
        for(int nk = 2; nk <= k; nk++) {
            
            for(int i = nk; i <= n; i++) {
                dp[i][nk] = Integer.MAX_VALUE;
                for(int j = 0; j < i; j++) {  
                    if(dp[i][nk] == Integer.MAX_VALUE || dp[i][nk] > Math.max(dp[j][nk-1], w[j+1][i]))  
                        dp[i][nk] = Math.max(dp[j][nk-1], w[j+1][i]);   
                }  
            }
        }
        return dp[n][k];
    }

http://jane4532.blogspot.com/2015/07/lintcode-copy-books.html

http://www.cnblogs.com/tonix/p/4858737.html

    int copyBooks(vector<int> &pages, int k) {
        size_t n = pages.size();
        if(k > n)
        {
            return *max_element(pages.begin(), pages.end());
        }

        //    Prefix Sums
        vector<long long> psum(n);
        for(int i = 0; i < n; i ++)
            psum[i] = i == 0? pages[i] : (psum[i - 1] + pages[i]);

        //  DP
        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, INT_MAX));
        for(int i = 1; i <= n; i ++)
            dp[i][1] = psum[i - 1];

        for(int i = 2; i <= k; i ++) // person
        for(int b = i; b <= n; b ++) // book
        for(int c = i-1; c < b; c ++) // prev book
        {
            long long last = dp[c][i - 1];
            long long cur  = psum[b-1] - psum[c - 1];
            dp[b][i] = min(dp[b][i], max(cur, last));
        }

        return dp[n][k];
    }

X. binary search with O(nlg(sum/k))

http://www.jiuzhang.com/solutions/copy-books/

// version 1: Binary Search
// this version cost O(n log m) where n is the number of books and m is the sum of the pages.

    public int copyBooks(int[] pages, int k) {
        if (pages.length == 0) {
            return 0;  
        }
        
        int total = 0;
        int max = pages[0];
        for (int i = 0; i < pages.length; i++) {
            total += pages[i];
            if (max < pages[i]) {
                max = pages[i];
            }
        }
        
        int start = max;
        int end = total;
        
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (countCopiers(pages, mid) > k) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (countCopiers(pages, start) <= k) {
            return start;
        }
        
        return end;
    }
    
    private int countCopiers(int[] pages, int limit) {
        if (pages.length == 0) {
            return 0;
        }
        
        int copiers = 1;
        int sum = pages[0]; // limit is always >= pages[0]
        for (int i = 1; i < pages.length; i++) {
            if (sum + pages[i] > limit) {
                copiers++;
                sum = 0;
            }
            sum += pages[i];
        }
        
        return copiers;
    }

http://blog.csdn.net/u012762106/article/details/47980483

https://github.com/iFighting/Lintcode/blob/master/Java/Copy-Books.java


	// time complexity: O(NlogM)(M = sum(pages[i]))
	public boolean isok(int[] pages, int num, int k) {
	int count = 0, cur = 0;
	for (int i = 0; i < pages.length; i ++) {
	if (cur + pages[i] > num) {
	count ++;
	cur = pages[i];
	} else {
	cur += pages[i];
	}
	}
	count ++;
	if (count <= k) return true;
	return false;
	}
	public int copyBooks(int[] pages, int k) {
	// write your code here
	int tot = 0, maxt = Integer.MIN_VALUE;
	for (int i = 0; i < pages.length; i ++) {
	tot += pages[i];
	maxt = Math.max(maxt, pages[i]);
	}
	int left = 0, right = tot, res = -1;
	while (left <= right) {
	int mid = left + (right - left) / 2;
	if (isok(pages, mid, k) && mid >= maxt) {
	right = mid - 1;
	res = mid;
	} else {
	left = mid + 1;
	}
	}
	return Math.max(res, maxt);
	}

http://www.chenguanghe.com/lintcode-copy-books/

public int copyBooks(int[] pages, int k) {

        // write your code here

        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;

    }

    public boolean search(int total, int[] page, int k) {

        int count = 0;

        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;

        }

        if(sum != 0)

            count++;

        return count <= k;

https://github.com/kamyu104/LintCode/blob/master/C++/copy-books.cpp
int copyBooks(vector<int> &pages, int k) {
if (k >= pages.size()) {
return *max_element(pages.cbegin(), pages.cend());
}

int sum = 0;
for (const auto& page : pages) {
sum += page;
}
int average = sum / k; // Lower bound.
return binarySearch(pages, k, average, sum);
}

int binarySearch(const vector<int> &pages,
const int k, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (valid(pages, k, mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}

// Check whether everyone copying at most x pages works or not.
bool valid(const vector<int> &pages, const int k, const int x) {
int sum = 0;
int people = 0;
for (int i = 0; i < pages.size() && people < k; ++i) {
if (sum + pages[i] > x) {
sum = 0;
++people;
}
sum += pages[i];
}
return people < k && sum <= x;
}

http://articles.leetcode.com/the-painters-partition-problem/

You have to paint N boards of length {A₀, A₁, A₂ … A_N-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

It turns out that this problem is the same as “FairWorkload” from TopCoder’s division 1 level 2 problem in SRM 169.

Now that we understand the problem better, we can re-state the above problem as follow:

Given an array of non-negative integers A and a positive integer k, we want to:
Divide A into k or fewer partitions,
such that the maximum sum over all the partitions is minimized.

X. brute force

int sum(int A[], int from, int to) {

  int total = 0;

  for (int i = from; i <= to; i++)

    total += A[i];

  return total;

}

int partition(int A[], int n, int k) {

  if (k == 1)

    return sum(A, 0, n-1);

  if (n == 1)

    return A[0];

  int best = INT_MAX;

  for (int j = 1; j <= n; j++)

    best = min(best, max(partition(A, j, k-1), sum(A, j, n-1)));

  return best;

}

It is exponential in run time complexity due to re-computation of the same values over and over again. We can do much better by caching our results in a kxN table utilizing Dynamic programming (DP). The table has to be constructed in a way such that the sub-problems are calculated first in a bottom-up fashion.

Each entry in the table needs O(N²) time to calculate. This is due to the summation term (∑{i=j..n-1} A_i) needs O(N) time, and on top of that you need to find the minimum across all partitions which increases the complexity by an order to O(N²). Since there are a total of kN entries in the table, the overall run time complexity has to be O(kN³).

It is easy to further reduce the complexity down to O(kN²). The extra calculation of the summation term (∑{i=j..n-1} A_i) can be easily avoided by caching the results using an array that stores cumulative sums.

Below is the DP solution with O(kN²) run time and using O(kN) space complexity.

const int MAX_N = 100;

int findMax(int A[], int n, int k) {

  int M[MAX_N+1][MAX_N+1] = {0};

  int cum[MAX_N+1] = {0};

  for (int i = 1; i <= n; i++)

    cum[i] = cum[i-1] + A[i-1];

  for (int i = 1; i <= n; i++)

    M[i][1] = cum[i];

  for (int i = 1; i <= k; i++)

    M[1][i] = A[0];

  for (int i = 2; i <= k; i++) {

    for (int j = 2; j <= n; j++) {

      int best = INT_MAX;

      for (int p = 1; p <= j; p++) {

        best = min(best, max(M[p][i-1], cum[j]-cum[p]));

      }

      M[j][i] = best;

    }

  }

  return M[n][k];

}

Could you think of another non DP algorithm which doesn’t requires any extra space?

http://articles.leetcode.com/the-painters-partition-problem-part-ii

int getMax(int A[], int n) {

  int max = INT_MIN;

  for (int i = 0; i < n; i++) {

     if (A[i] > max) max = A[i];

}

  return max;

}

int getSum(int A[], int n) {

  int total = 0;

  for (int i = 0; i < n; i++)

    total += A[i];

  return total;

}

int getRequiredPainters(int A[], int n, int maxLengthPerPainter) {

  int total = 0, numPainters = 1;

  for (int i = 0; i < n; i++) {

    total += A[i];

    if (total > maxLengthPerPainter) {

      total = A[i];

      numPainters++;

}

}

  return numPainters;

}

int partition(int A[], int n, int k) {

  int lo = getMax(A, n);

  int hi = getSum(A, n);

  while (lo < hi) {

    int mid = lo + (hi-lo)/2;

    int requiredPainters = getRequiredPainters(A, n, mid);

    if (requiredPainters <= k)

      hi = mid;

    else

      lo = mid+1;

}

  return lo;

}

The above binary search solution has a run time complexity of O(N log ( ∑ Ai )). What impact would the term ? Ai (ie, the search space) have over the run time itself? What if the search space is extremely large?

As you may have known, binary search is extremely fast. For example, binary search in a range of one million elements requires no more than 20 iterations. Here, we explore an alternative solution which reduces the search space even further.

Find the index j such that B[j] fails to satisfy the condition while B[j+1] satisfy.

Finally, we can set lo = B[j] and hi = B[j+1], and apply the same binary search from method 1 from above.

Using the above example:

A = { 100, 200, 300, 400, 500, 600, 700, 800, 900 }, and k = 3.

We build the cumulative array B:

B = { 100, 300, 600, 1000, 1500, 2100, 2800, 3600, 4500 }

After we apply binary search, we are able to find that B[4] = 1500, B[5] = 2100, because for costmax = 1500, x = 4; while costmax = 2100, x =3.

Time required: O(N log N)

Then, we set lo = 1500 and hi = 2100, then apply binary search to find in that range.

Time required: O(N log (B[j+1]-B[j]) ) = O(N log A[j+1]).

Therefore, the worst case run time complexity = O(N log N + N log max(A) )

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

http://www.geeksforgeeks.org/allocate-minimum-number-pages/

https://www.jiuzhang.com/solutions/copy-books/
Read full article from Copy Books | The Walking Dad

LintCode 437 - Copy Books

Solution

O(n^2 * k) solution

X. O(n * k) solution

Labels

Popular Posts