87. Painter's Partition Problem

There are n boards with given lengths and k painters. Painting one unit of board length takes one unit of time, each painter paints a contiguous, non-empty range of boards, and painters work in parallel. Find the minimum time needed to paint all boards, given an optimal contiguous partition among the k painters.

Input: The first line contains an integer n. The second line contains n space-separated integers, the board lengths. The third line contains the integer k, the number of painters. Output: Print a single integer - the minimum time needed to paint all boards.

1 <= k <= n <= 10^4

The greedy feasibility check (assign boards to the current painter until they'd exceed T, then move to a new painter) is itself provably optimal for a FIXED T - it always uses the fewest possible painters for that specific time limit, which is exactly what the outer binary search needs to trust.

Split a row of boards among several painters (each getting a contiguous chunk) working in parallel, minimizing the maximum time any single painter spends. Brute force: Try every possible way of splitting the boards into k contiguous groups directly, computing each split's maximum painter-time - this is combinatorially expensive (many possible partition points), impractical for larger n. Optimised: Since 'can this maximum time T be achieved with k or fewer painters' is a MONOTONIC condition (larger T is always at least as easy to satisfy), binary searching on T with an O(n) greedy feasibility check at each candidate reduces an expensive combinatorial search to O(n log(sum of pages)).

Define dp[i][j] as the minimum possible 'maximum load' when optimally partitioning the first i boards among j painters. To compute dp[i][j], try every possible position p for where the j-th painter's segment starts, taking the better of dp[p][j-1] and the sum of boards from p+1 to i, and minimize over all choices of p. This reuses overlapping subproblems instead of re-deriving every partition from scratch, turning the combinatorial brute force into a polynomial-time table fill. Time: O(n^2 * k) Space: O(n*k)

Binary search over the candidate answer time T, ranging from the single longest board (the minimum possible answer) to the sum of all board lengths (one painter does everything). For a given T, greedily check feasibility by scanning the boards left to right, assigning boards to the current painter until adding the next one would exceed T, at which point a new painter starts; if the number of painters needed is at most k, T is achievable. This greedy feasibility check runs in linear time, and binary searching over T multiplies that by only a logarithmic factor, which is far faster than filling an entire DP table and is the standard optimal technique for these 'minimize the maximum' partition problems. Time: O(n log(sum of lengths)) Space: O(1)

Recursively try every way of choosing k-1 split points among the n boards to divide them into k contiguous, non-empty groups, compute the maximum group sum for each complete partition (since painters work in parallel, the total time is dictated by whichever painter has the most board length), and keep the overall minimum across all partitions. This is guaranteed correct since it examines every valid partition, but the number of ways to place k-1 dividers among n-1 gaps grows combinatorially, making this infeasible for anything but tiny inputs. Time: O(C(n-1, k-1)) Space: O(k)

1. Binary search on the candidate answer T (the maximum time any one painter takes). 2. For a candidate T, greedily check feasibility: walk through the boards, assigning them to the CURRENT painter as long as adding the next board doesn't push that painter's total past T; once it would, start a new painter. 3. If the number of painters needed is <= k, T is feasible - try a SMALLER T; otherwise, try a LARGER one.

Time: O(n log(sum of all board lengths)) - each binary search step's greedy feasibility check costs O(n). Space: O(1) extra space beyond the input array.

Test k = n (each painter gets exactly one board, answer is the longest board), k = 1 (one painter does everything, answer is the total length), and n = 10^4 for performance.

Be ready to connect this directly to 'Book Allocation Problem' - both are literally the same underlying technique (binary search on the answer, greedy feasibility check), just described with different real-world framing.