DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Minimize max distance to gas station

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)