Painters Partition Problem

The problem, simply

You get a row of boards with lengths, and k painters. Painting 1 unit of board takes 1 minute. All painters work at the same time. Each painter must paint boards that stand next to each other (one unbroken stretch), and every board is painted by exactly one painter.

The job is done when the slowest painter is done. Give back the smallest possible finishing time.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every way to cut the row into k stretches and keep the best.

1. The first painter takes boards 0..i for some i.
2. The other k - 1 painters split the rest in the best way, which is the same problem again.
3. This plan finishes at max(first painter's time, best time for the rest). Try every i and keep the smallest.
4. With one painter left, that painter takes everything.

class Solution {
    public long minTime(int[] boards, int k) {
        return best(boards, 0, Math.min(k, boards.length));
    }

    // best finishing time for boards[start..] with k painters
    private long best(int[] boards, int start, int k) {
        int n = boards.length;
        if (k == 1) {
            long sum = 0;
            for (int i = start; i < n; i++) sum += boards[i];
            return sum;                       // one painter takes the rest
        }
        long result = Long.MAX_VALUE, first = 0;
        for (int i = start; i <= n - k; i++) { // leave at least one board for each other painter
            first += boards[i];
            long rest = best(boards, i + 1, k - 1);
            result = Math.min(result, Math.max(first, rest));
        }
        return result;
    }
}

How long it takes: the number of ways to place k - 1 cuts grows like n^(k-1), and each way adds up a stretch, so about O(n^k). Extra room: the calls go k deep, O(k).

Way 2: the clever way

Guess the answer, check the guess quickly, and binary search the guesses.

1. The smallest possible answer is the longest board, lo = max(boards). Nobody can split a board.
2. The biggest possible answer is one painter doing everything, hi = sum(boards).
3. canFinish(limit): walk along the boards and keep adding to the current painter. When the next board would push them over limit, start a new painter. If you need more than k painters, the answer is no.
4. If canFinish(mid) is yes, mid might be the answer, but try smaller: hi = mid - 1. If no, go bigger: lo = mid + 1.

Filling each painter as much as possible is safe: giving a painter fewer boards never helps the painters after them.

class Solution {
    public long minTime(int[] boards, int k) {
        long lo = 0, hi = 0;
        for (int b : boards) { lo = Math.max(lo, b); hi += b; }
        long answer = hi;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (canFinish(boards, k, mid)) {
                answer = mid;          // mid works, try a smaller time
                hi = mid - 1;
            } else {
                lo = mid + 1;          // too fast, give more time
            }
        }
        return answer;
    }

    private boolean canFinish(int[] boards, int k, long limit) {
        int painters = 1;
        long load = 0;
        for (int b : boards) {
            if (load + b > limit) {    // this board does not fit: next painter
                painters++;
                load = 0;
                if (painters > k) return false;
            }
            load += b;
        }
        return true;
    }
}

How long it takes: the range of times is sum - max wide, so there are O(log(sum)) guesses, and each check walks the boards once, O(n log(sum)). Extra room: O(1).

Watch out for

• Sums of many long boards overflow int. Use long for hi, mid and load.
• More painters than boards is fine. The answer is just the longest board.
• If each unit takes t minutes instead of 1, find the answer the same way and multiply by t at the end.
• Returning lo at the end also works with this loop, because lo ends one past the last "no".

What interviewers ask next

• Book allocation, split array largest sum, and ship packages within D days are the same problem with a different story. Recognize "minimize the biggest part" as binary search on the answer.
• Aggressive cows flips it: maximize the smallest gap. Binary search the gap and check greedily whether all cows fit.
• Can you do it with dynamic programming? dp[j][i] = best time for the first i boards with j painters, trying every last cut. That is O(k n^2), slower but it gives the exact split easily.
• Print the actual split. Run canFinish(answer) once more and record where each painter starts.

Remember this

Grown-up words: guessing the time and checking it is binary search on the answer, the yes-then-stays-yes shape is monotonicity, filling each painter as much as possible is the greedy feasibility check, and the general problem is the linear partition problem.