Marathon Water Stops
Medium · binary search
A marathon is run along a straight road. The list stations gives the positions, in metres from the start, of the water stations that already exist. The positions are whole numbers in strictly increasing order.
The organisers may build up to k new water stations. Each one goes at a whole-number position between the first and the last existing station, and no two stations (old or new) may share a position.
After building, look at every pair of neighbouring stations (old or new) and take the distance between them. The longest gap is the largest of those distances.
Return the smallest longest gap that the organisers can reach by choosing where to build their new stations.
Examples
Example 1
Input: stations = [0, 10, 25, 30], k = 2
Output: 8
The gaps are 10, 15 and 5. Build one station in the 10 gap (two gaps of 5) and one in the 15 gap (gaps of 7 and 8). The longest gap is then 8, and no placement does better.
Example 2
Input: stations = [3, 4, 5, 6], k = 3
Output: 1
Every gap is already 1, and extra stations cannot shorten a gap below 1.
Constraints
- 2 <= len(stations) <= 10^5
- 0 <= stations[i] <= 10^9, in strictly increasing order
- 0 <= k <= 10^9