Radio Dial Spacing
Medium · binary search
A regulator is placing radio stations on a dial. The stations come in a fixed order, and each one has a licence window: station i may broadcast on any whole-number frequency from low[i] to high[i], both included.
The stations must appear on the dial in the listed order, so each station's frequency has to be at least the frequency of the station before it. Two neighbours may even share a frequency, but that would make them interfere badly. The regulator wants the neighbours to be as far apart as possible: the gap between stations i and i + 1 is frequency[i + 1] - frequency[i], and the aim is to make the *smallest* gap as large as it can be.
Choose a frequency for every station and return the largest value that the smallest gap between neighbouring stations can take.
Examples
Example 1
Input: low = [0, 4, 6], high = [3, 9, 20]
Output: 9
Use frequencies 0, 9 and 18: both gaps are 9. A smallest gap of 10 is impossible, because the second station would have to sit on 10 or higher and its window ends at 9.
Example 2
Input: low = [10, 10], high = [10, 10]
Output: 0
Both stations are forced onto frequency 10, so the gap is 0.
Constraints
- 2 <= len(low) <= 10^4
- len(high) == len(low)
- 0 <= low[i] <= high[i] <= 10^9
- low[i] <= low[i + 1] (the windows start in dial order)