Two Board Hole Cover
MediumBinary Search · Microsoft
Holes are drilled in a long plank at integer positions holes (unsorted; a position may repeat). You will cover them with exactly two boards of the same length L, where L is a positive integer.
A board of length L placed at integer position x covers every hole at a position p with x <= p <= x + L (both ends included). The boards may overlap, and a board may cover no holes.
Return the smallest L for which two such boards can cover all the holes.
Example 1
- Input:
- holes = [17, 4, 9, 30, 25]
- Output:
- 13
- Explanation
- Sorted, the holes are 4, 9, 17, 25, 30. Covering 4 to 17 with one board needs length 13, and 25 to 30 needs only 5, so
L = 13works. Every other split leaves one board needing at least 13.
Example 2
- Input:
- holes = [1, 2, 3, 100, 101]
- Output:
- 2
- Explanation
- One board covers 1 to 3 (length 2) and the other covers 100 to 101 (length 1), so length 2 is enough for both.
Example 3
- Input:
- holes = [8]
- Output:
- 1
- Explanation
- A single hole needs no real length, but the board length must be a positive integer, so the answer is 1.
Constraints
1 <= holes.length <= 10^5-10^9 <= holes[i] <= 10^9