49. Aggressive Cows

Topic :

binary search

Difficulty :

medium

Problem Link :

problem statement

You are given an array consisting of n integers which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. You are given the task of assigning stalls to k cows such that the minimum distance between any two of them is the maximum possible.
The first line of input contains two space-separated integers n and k.
The second line contains n space-separated integers denoting the position of the stalls.

Example 1:

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

Output:
3

Explanation:
The first cow can be placed at stalls[0], 
the second cow can be placed at stalls[2] and 
the third cow can be placed at stalls[3]. 
The minimum distance between cows, in this case, is 3, 
which also is the largest among all possible ways.

Example 2:

Input:
n=5 
k=3
stalls = [10 1 2 7 5]

Output:
4

Explanation:
The first cow can be placed at stalls[0],
the second cow can be placed at stalls[1] and
the third cow can be placed at stalls[4].
The minimum distance between cows, in this case, is 4,
which also is the largest among all possible ways.

Complete the function int solve(), which takes integer n, k, and a vector stalls with n integers as input and returns the largest possible minimum distance between cows.

solution

import java.io.*;
import java.util.*;
class AggressiveCows
{
   public static void main (String args[])
   {
       int stalls[]={1,2,4,8,9};
       int n=5;
       int cows=3;
       System.out.println(minMaxDistance_bw_Cows(n,stalls,cows));
    }
   static boolean isPossible(int stalls[],int n,int cows, int minDist){
     int count_cows=1;
     int lastPlacedCow=stalls[0]; // place the first cow
     
     for(int i=1;i<n;i++)
     {
         if(stalls[i]-lastPlacedCow>=minDist) // if the cow can be placed
          {   count_cows++;
              lastPlacedCow=stalls[i];
          }
      }
     if(count_cows>=cows) // if the cows can be placed
     {
         return true;
      }
      else
      return false;
  }
    static int minMaxDistance_bw_Cows(int n,int[]stalls, int cows)
  {
        Arrays.sort(stalls);
        int low=1; //minimum distance between 2 cows
        int high=stalls[n-1]-stalls[0]; //max distance bewteen 2 cows
        
        while(low<=high)
        {
            int mid=low+(high-low)/2;
            if(isPossible(stalls,n,cows,mid)) // if the cows can be placed then we have  to try for greater min distance
             { low=mid+1; 
                }
              else // if the cows cannot be placed then we have to try for lesser min distance
              {
             high=mid-1;       
           }
       }
       return high;
  }
}