LintCode 437 · Copy Books.java

Binary Search:
note that: "This one is tricky."

	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;
	}
	int begin = 0;
	int end = getSum(pages);
	while (begin + 1 < end) {
	int mid = (end - begin) / 2 + begin;
	if (k >= getNumberOfCopiers(pages, mid)) {
	end = mid;
	} else {
	begin = mid;
	}
	}
	if (k >= getNumberOfCopiers(pages, begin)) {
	return begin;
	}
	if (k >= getNumberOfCopiers(pages, end)) {
	return end;
	}
	return Integer.MAX_VALUE;
	}
	private int getNumberOfCopiers(int[] pages, int timeLimit) {
	int copiers = 0;
	int alreadyCopied = timeLimit;
	for (int page : pages) {
	if (page > timeLimit) {
	return Integer.MAX_VALUE;
	}
	if (alreadyCopied + page > timeLimit) {
	copiers++;
	alreadyCopied = 0;
	}
	alreadyCopied += page;
	}
	return copiers;
	}
	private int getSum(int[] pages) {
	int sum = 0;
	for (int page : pages) {
	sum += page;
	}
	return sum;
	}
	}

view raw 437 · Copy Books.java hosted with ❤ by GitHub