Aggressive Cows

Aggressive Cows

we need to place cows in stalls such that the minimum distance between any two cows is maximized.

bool isPossible(vector<int> &stalls, int k, int mid, int n) {
    int cowCount = 1; // Start by placing the first cow in the first stall
    int lastPos = stalls[0]; // Track the last position where a cow was placed

    // Iterate through all stalls
    for(int i=0; i<n; i++ ){
        // Check if the current stall can accommodate a cow with at least 'mid' distance
        if(stalls[i] - lastPos >= mid) {
            cowCount++; // Place a cow
            // If we've placed all k cows, return true
            if(cowCount == k) {
                return true;
            }
            lastPos = stalls[i]; // Update the last position
        }
    }
    return false; // Not enough cows placed
}


int aggressiveCows(vector<int> &stalls, int k) {
    // Sort the stall positions
    sort(stalls.begin(), stalls.end());

    int s = 0; // Start of the search range
    int n = stalls.size(); // Total number of stalls
    int e = stalls[n - 1]; // End of the search range (last stall position)
    int ans = -1; // To store the final answer
    int mid = s + (e - s) / 2; // Calculate the mid-point for binary search

    // Perform binary search
    while(s <= e) {
        // Check if placing cows with at least 'mid' distance is possible
        if(isPossible(stalls, k, mid, n)) {
            ans = mid; // If possible, store the answer
            s = mid + 1; // Try for a larger distance
        }
        else {
            e = mid - 1; // Try for a smaller distance
        }
        mid = s + (e - s) / 2; // Update mid-point
    }
    return ans; // Return the maximum minimum distance
}

Example

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.