[Question] We have an horizontal number line. On that number line, we have gas stations at positions stations[0], stations[1], …, stations[N-1], where N = size of the stations array. Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized. We have to find the smallest possible value of D. Find the answer exactly to 2 decimal places.
Example 1:
Input: N = 10 stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] K = 9 Output: 0.50 Explanation: Each of the 9 stations can be added mid way between all the existing adjacent stations.
Example 2:
Input:
N = 10
stations = [3,6,12,19,33,44,67,72,89,95]
K = 2
Output: 14.00
// TC: O(Nlog(N))
// SC: O(1)
func isPossibleToPlace(_ stations: [Int],_ x: Double) -> Int {
var station_count = 0
for i in 0..<stations.count - 1 {
let distance = Double(stations[i + 1] - stations[i])
station_count += Int(ceil(distance / x)) - 1
}
return station_count
}
func findSmallestMaxDist(_ stations: [Int], _ k: Int) ->Double {
// Code here
var low = 0.0;
var n = stations.count
var high = Double(stations[n - 1] - stations[0])
while (high - low) > 0.000001 {
var mid = Double(low + high) / 2
var x = isPossibleToPlace(stations, mid)
if x > k {
low = mid
} else {
high = mid
}
}
return high
}
let gasStationArray = [3,6,12,19,33,44,67,72,89,95]
let gasStationToBeInsert = 2
let gasStationDistance = findSmallestMaxDist(gasStationArray, gasStationToBeInsert)
print(" gasStationDistance -- ", gasStationDistance)// 14