Aggresive Cows

https://www.geeksforgeeks.org/problems/aggressive-cows/1

You are given:

n stalls positioned at different locations along a line (given as an array of integers).
k cows that you need to place in these stalls.
You want to place the cows in such a way that the minimum distance between any two cows is as large as possible.




"minimum largest" terminology, consider this:

If you put cows at 1,2,8. Distance btw stalls is 1, 6 resp. 
but if you keep at 1,4,8 distance is 3, 4. 
In the first case, the minimum distance is 1 while in the 2nd case it's 3. 

You can never put cows in a way that gives a minimum that is larger than 3 i.e. distance cannot be 4,5 or 6,7.







Input:
stalls = [1, 2, 4, 8, 9]
k = 3

Output:
3



1,2,4,8,9

i have 3 stalls


so i need to place them such that

1         2          4           8         9


One stall i can place like this :

I can place at 2-4 -> 2 - 3 - 4
then the distance will be 

1-2 =1
2-3=1
3-4=1
4-8=4
8-9=1


minimze the maximum means now in the distqnces b/w stalls

nowout of all the maximum distance is 4





now I will place one more stall here:

1         2     3      4     6   7    8         9

I can place at  -> 
then the distance will be 

all distnces are 1
so mimimizing the max is 1.




so what are all the points i have where i can place the cows stalls
so i will put the cows in stall and check all possibilities and backtrck and continue.
Not optimised.




BS+Greedy:



SORT the stall if not already.



the range : 

min distance - low will be starting stall
max - max(stall) - min(stall)

so the max distance would be the starting stall - ending stall

min ? is 1 or? there is only one stall.
they are placed side by side



______________________________________



How to decide if we move left or right.
-> if i can place the cos with lets a distance.
I will check if i can check if i can place the more distance.



class Solution {
  public:
  
  
    bool canPlace(vector<int> &stalls, int k, int minDistance){
        
        //so start from the starting, and check 
        //and place the cow, after the min distance
        int cowsPlaced=1 , lastPos=stalls[0];
        
        for(int i=1;i<stalls.size();i++){
            
            
            if(stalls[i]-lastPos>=minDistance){
                cowsPlaced+=1;
                lastPos=stalls[i];
            }
            
            
        }
        return cowsPlaced>=k;
            
    }
    
    
    
    int aggressiveCows(vector<int> &stalls, int k) {
        
        //sort
         sort(stalls.begin(),stalls.end());
         int n=stalls.size();
         
         //min distance =1, placing cow side by side
         //max distance - max distance b/w the start and  stall
          int l=1,dis=0;
          int h=stalls[n-1]-stalls[0];
          
          while(l<=h){
              
              int mid = l+(h-l)/2;
              
              //if i can place this with the distance b/w stalls
              //should i move left or right.
              //
              if(canPlace(stalls,k,mid)){
                  dis = mid;
                 l=mid+1;
                  
              }
              
              else h=mid-1;
              
          }
          
          return dis;
        
    }
};







// The actual greedy idea

// Place the first cow at stalls[0].
// Keep track of the last position where you placed a cow (lastPos).

// For every next stall:
// If stalls[i] - lastPos >= minDistance, place another cow at stalls[i].
// Update lastPos = stalls[i].
// Keep a counter cowsPlaced.


// If cowsPlaced >= k → return true.

// Otherwise → return false.



We want to maximize the min distance.
So each time placement with distance mid succeeds, we ask:
 Can I push the cows even farther apart?
That’s why we go right.

If it fails, it means we asked for too large a min distance, so we must reduce → go left.