Copy Books

Binary search

The countPeople method is very important.
We should consider if we have to add 1 more person if that person is doing some tasks.

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 || k <= 0) return 0;
        //left -> max #page of 1 book
        //right -> sum of all books
        int left = 0, right = 0;
        for (int i = 0; i < pages.length; i++) {
            left = Math.max(left, pages[i]);
            right += pages[i];
        }
        int mid, people;
        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            //given time mid and pages, how many people is needed to finish the work
            people = countPeople(mid, pages);
            if (people <= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        people = countPeople(left, pages);
        if (people <= k) return left;
        else return right;
    }
    private int countPeople(int time, int[] pages) {
        int people = 0, total = 0;
        for (int i = 0; i < pages.length; i++) {
            if (total + pages[i] > time) {
                people++;
                total = 0;
            }
            total += pages[i];
        }
        people += total > 1 ? 1 : 0;
        return people;
    }
}