Painter's Partition

Painter’s Partition

#include <iostream>
#include <vector>
#include <numeric> // for std::accumulate
using namespace std;

// Function to check if it's possible to paint the boards within given maxTime
bool isPossible(const vector<int>& boards, int k, long long maxTime) {
    int painterCount = 1; // Start with one painter
    long long timeSpent = 0; // Time spent by the current painter

    for (int length : boards) {
        // If the current board length exceeds maxTime, it's not possible
        if (length > maxTime) return false;

        timeSpent += length; // Add board length to the current painter's time
        if (timeSpent > maxTime) { // If time exceeds maxTime, use a new painter
            painterCount++;
            timeSpent = length; // Reset time for the new painter
        }
    }
    return painterCount <= k; // Check if the number of painters used is within limit
}

// Main function to find the minimum time required to paint the boards
long long painterPartition(const vector<int>& boards, int k) {
    long long s = *max_element(boards.begin(), boards.end()); // Lower bound
    long long e = accumulate(boards.begin(), boards.end(), 0LL); // Upper bound
    long long ans = e; // Initialize answer with upper bound

    // Binary search for the optimal solution
    while (s <= e) {
        long long mid = s + (e - s) / 2; // Calculate mid-point

        // Check if it's possible to paint within mid time
        if (isPossible(boards, k, mid)) {
            ans = mid; // Update answer
            e = mid - 1; // Search for a smaller maximum time
        } else {
            s = mid + 1; // Increase minimum time
        }
    }
    return ans; // Return the minimum maximum time
}

int main() {
    vector<int> boards = {10, 20, 30, 40}; // Lengths of the boards
    int k = 2; // Number of painters

    long long minTime = painterPartition(boards, k); // Calculate minimum time
    cout << "Minimum time required to paint all boards: " << minTime << endl;

    return 0;
}

Example

Consider the following input:

stalls = {1, 2, 4, 8, 9} // positions of stalls
k = 3 // number of cows

1. Initial Setup:

   • Sort the stalls: {1, 2, 4, 8, 9}
   • Set search boundaries:
     • s = 0 (minimum possible distance)
     • e = 9 (maximum possible distance)
     • ans = -1

2. Binary Search Process:

   • First Iteration:
     • mid = (0 + 9) / 2 = 4
     • Check if we can place 3 cows with a minimum distance of 4 using isPossible.
     • Placement:
       • Place first cow at 1
       • Next possible position for cow is 5, but it’s not available. Thus, place second cow at 4.
       • Not enough cows placed.
     • Result: not possible, update e = mid - 1 = 3.
   • Second Iteration:
     • mid = (0 + 3) / 2 = 1
     • Check if we can place 3 cows with a minimum distance of 1.
     • Placement:
       • Place first cow at 1
       • Place second cow at 2
       • Place third cow at 4
     • Result: possible, update ans = 1 and s = mid + 1 = 2.
   • Third Iteration:
     • mid = (2 + 3) / 2 = 2
     • Check if we can place 3 cows with a minimum distance of 2.
     • Placement:
       • Place first cow at 1
       • Place second cow at 4
       • Not enough cows placed.
     • Result: not possible, update e = mid - 1 = 1
   • Fourth Iteration:
     • mid = (2 + 1) / 2 = 3
     • Check if we can place 3 cows with a minimum distance of 3.
     • Placement:
       • Place first cow at 1
       • Next possible position for cow is 4 (place second cow here).
       • Not enough cows placed.
     • Result: not possible, update e = mid - 1 = 2.

3. Final Result:

   • The loop continues until s > e. The maximum minimum distance is found to be 1.