Aggressive Cows Maximum Minimum Distance in DSA C++ - Build from Scratch

Aggressive Cows Maximum Minimum Distance

📖 Scenario: You are managing a farm with several stalls placed along a straight line. You want to place cows in these stalls such that the minimum distance between any two cows is as large as possible. This helps reduce fights between cows.

🎯 Goal: Build a program that finds the largest minimum distance possible between cows placed in the given stalls.

📋 What You'll Learn

Create a vector called stalls with the exact stall positions: 1, 2, 8, 4, 9

Create an integer variable called cows and set it to 3

Write a function canPlaceCows that checks if cows can be placed with at least a given minimum distance

Use binary search to find the maximum minimum distance to place all cows

Print the maximum minimum distance found

💡 Why This Matters

🌍 Real World

This problem models placing resources or people in locations to maximize minimum spacing, useful in agriculture, networking, and event planning.

💼 Career

Understanding binary search on answer space and greedy checking is important for coding interviews and optimization problems.

1

Create the stalls vector

Create a vector of integers called stalls with these exact values: 1, 2, 8, 4, 9

DSA C++

# Create the vector stalls with the given stall positions
# Your code here

Hint

Use std::vector<int> and initialize it with the given numbers inside curly braces.

2

Set the number of cows

Create an integer variable called cows and set it to 3

DSA C++

#include 

std::vector stalls = {1, 2, 8, 4, 9};

// Create the integer variable cows and set it to 3
# Your code here

Hint

Use int cows = 3; to create the variable.

3

Write the function to check placement feasibility

Write a function called canPlaceCows that takes const std::vector<int>& stalls, int cows, and int minDist as parameters and returns bool. The function should check if it is possible to place all cows in stalls so that the minimum distance between any two cows is at least minDist. Use a greedy approach starting from the first stall after sorting.

DSA C++

#include 
#include 

std::vector stalls = {1, 2, 8, 4, 9};

int cows = 3;

// Write the function canPlaceCows below
# Your code here

Hint

Sort the stalls first before calling this function. Use a loop to count how many cows can be placed with at least minDist distance.

4

Find and print the maximum minimum distance

Sort the stalls vector. Use binary search with variables low and high to find the largest minimum distance to place all cows. Print the maximum minimum distance found using std::cout.

DSA C++

#include 
#include 
#include 

std::vector stalls = {1, 2, 8, 4, 9};

int cows = 3;

bool canPlaceCows(const std::vector& stalls, int cows, int minDist) {
    int count = 1; // Place first cow in first stall
    int last_position = stalls[0];
    for (size_t i = 1; i = minDist) {
            count++;
            last_position = stalls[i];
            if (count == cows) {
                return true;
            }
        }
    }
    return false;
}

// Sort stalls and find max minimum distance using binary search
# Your code here

Hint

Use binary search between 1 and the maximum distance between the first and last stall. Update the result when placement is possible.