Minimize max distance to gas station
class Solution {
public double minMaxDist(int[] stations, int K) {
// code here
double min = 0;
double max = 0;
for(int i =1;i<stations.length;i++){
max = Math.max(max,stations[i]-stations[i-1]);
}
double result = 0.000000;
while(max-min > 1e-6){
double mid = (min+max)/2.0;
if(isPossible(mid,K, stations)){
max = mid;
}
else min = mid;
}
return max;
}
public boolean isPossible(double dis, int K , int stations[]){
int count =0;
for(int i = 1;i< stations.length;i++){
double gap = stations[i]-stations[i-1];
count+= (int) (gap/dis);
if(gap % dis==0) count--; // very important because if gap is exactly divisible then adding (quotient) no of stations in between i and i-1 wouuld reduce the min distance lower than dis(check value)
}
return count<=K;
}
}
Top comments (0)