Welcome to Subscribe On Youtube

774. Minimize Max Distance to Gas Station

Description

You are given an integer array stations that represents the positions of the gas stations on the x-axis. You are also given an integer k.

You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position.

Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations.

Return the smallest possible value of penalty(). Answers within 10-6 of the actual answer will be accepted.

 

Example 1:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

Example 2:

Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1
Output: 14.00000

 

Constraints:

• 10 <= stations.length <= 2000
• 0 <= stations[i] <= 108
• stations is sorted in a strictly increasing order.
• 1 <= k <= 106

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public double minmaxGasDist(int[] stations, int k) {
          double left = 0, right = 1e8;
          while (right - left > 1e-6) {
              double mid = (left + right) / 2.0;
              if (check(mid, stations, k)) {
                  right = mid;
              } else {
                  left = mid;
              }
          }
          return left;
      }
  
      private boolean check(double x, int[] stations, int k) {
          int s = 0;
          for (int i = 0; i < stations.length - 1; ++i) {
              s += (int) ((stations[i + 1] - stations[i]) / x);
          }
          return s <= k;
      }
  }
  

• class Solution {
  public:
      double minmaxGasDist(vector<int>& stations, int k) {
          double left = 0, right = 1e8;
          auto check = [&](double x) {
              int s = 0;
              for (int i = 0; i < stations.size() - 1; ++i) {
                  s += (int) ((stations[i + 1] - stations[i]) / x);
              }
              return s <= k;
          };
          while (right - left > 1e-6) {
              double mid = (left + right) / 2.0;
              if (check(mid)) {
                  right = mid;
              } else {
                  left = mid;
              }
          }
          return left;
      }
  };
  

• class Solution:
      def minmaxGasDist(self, stations: List[int], k: int) -> float:
          def check(x):
              return sum(int((b - a) / x) for a, b in pairwise(stations)) <= k
  
          left, right = 0, 1e8
          while right - left > 1e-6:
              mid = (left + right) / 2
              if check(mid):
                  right = mid
              else:
                  left = mid
          return left
  
  

• func minmaxGasDist(stations []int, k int) float64 {
  	check := func(x float64) bool {
  		s := 0
  		for i, v := range stations[:len(stations)-1] {
  			s += int(float64(stations[i+1]-v) / x)
  		}
  		return s <= k
  	}
  	var left, right float64 = 0, 1e8
  	for right-left > 1e-6 {
  		mid := (left + right) / 2.0
  		if check(mid) {
  			right = mid
  		} else {
  			left = mid
  		}
  	}
  	return left
  }
  

All Problems

All Solutions