Solution: Minimize Max Distance to Gas Station
Explore how to minimize the largest gap between gas stations by strategically adding new stations along a line. Learn to apply modified binary search over continuous values to find the smallest possible maximum distance, and understand when to stop the search based on numerical precision. This lesson helps you efficiently solve placement problems by assessing gaps and using tradeoffs between placement count and maximum distance.
We'll cover the following...
Statement
You are given an integer array, stations, representing the positions of existing gas stations along the x-axis. You are also given an integer k, indicating the number of additional gas stations you must add. These new gas stations can be placed at any position along the x-axis, including non-integer locations.
A penalty is the maximum distance between two adjacent gas stations after placing the k new stations. Your task is to return the smallest possible value of this penalty. An answer is correct if it is within
Constraints:
...