There are N holes arranged in a row in the top of an old table. We want to fix the table by covering the holes with two boards. For technical reasons, the boards need to be of the same length.
The position of the K-th hole is A[K]. What is the shortest length of the boards required to cover all the holes? The length of the boards has to be a positive integer. A board of length L, set at position X, covers all the holes located between positions X and X + L (inclusive). The position of every hole is unique.
Write a function:
def solution(A)that, given an array A of integers of length N, representing the positions of the holes in the table, returns the shortest board length required to cover all the holes.
Examples:
- Given A = [11, 20, 15], your function should return 4. The first board would cover the holes in positions 11 and 15, and the second board the hole at position 20.
- Given A = [15, 20, 9, 11], your function should return 5. The first board covers the holes at positions 9 and 11, and the second one the holes in positions 15 and 20.
- Given A = [0, 44, 32, 30, 42, 18, 34, 16, 35], your function should return 18. The first board would cover the holes in positions between 0 and 18, and the second the positions between 30 and 44.
- Given A = [9], your function should return 1.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000]
- each element of array A is an integer within the range [0..1,000,000,000]
- the elements of A are all distinct
这题的关键是把所有孔的位置排序后，考虑用两块同样长度的木板覆盖排序后的点集。对于固定长度 L，可以贪心地从最左边开始放一块木板，尽量覆盖更多连续孔洞；一旦当前孔超出覆盖范围，就再放第二块。判断某个 L 是否可行后，可以用二分查找寻找最小可行长度。整体思路是“排序 + 贪心检查 + 二分答案”，时间复杂度约为 O(N log N)，适合处理 10 万级别数据。
