The Painter's Partition Problem-II

JavaView on GFG

Intuition

Same as Capacity to Ship / Split Array Largest Sum. Binary search on maximum length any one painter paints.

Algorithm

1lo=max(boards), hi=sum(boards).
2Feasibility(mid): greedily assign boards, count painters needed <= k.
3Return minimum feasible mid.

Common Pitfalls

•Greedy: fill each painter as much as possible without exceeding mid. Count total painters needed.

The Painter's Partition Problem-II.java

Java

// Approach: Binary search on max load. Greedily assign boards to painters; check if k painters suffice.
// Time: O(n log(sum)) Space: O(1)
class Solution {
    public int minTime(int[] arr, int k) {
        int l = 1, h = 10000000, ans = -1;
        while (l <= h) {
            int md = l + (h - l) / 2;
            if (k >= check(md, arr)) {
                ans = md;
                h = md - 1;
            } else
                l = md + 1;
        }
        
        return ans;
    }

    private int check(int md, int[] arr) {
        int n = arr.length, sm = 0, k = 1;
        for (int i = 0; i < n; i++) {
            if (arr[i] > md)
                return Integer.MAX_VALUE;
            sm += arr[i];
            if (sm > md) {
                k++;
                sm = arr[i];
            }
        }

        return k;
    }
}

Was this solution helpful?