如何求k个等长线段覆盖n个点的最小长度L？要求O(nlogn)时间复杂度

前提边界处理 #

当 n <= k 时，每个点可以单独用一个长度为0的线段覆盖，因此最小L直接取0即可。

n > k 场景的核心解法 #

1. 预处理排序 #

首先将所有n个点的坐标从小到大排序，时间复杂度为O(nlogn)。

2. 二分答案定位最小L #

由于L的可行性满足单调性质：若长度L0可使用不超过k个线段覆盖所有点，则所有大于等于L0的L都一定可行，因此可以通过二分法快速缩小范围找到最小的可行L：

• 二分初始左边界为0，初始右边界为排序后最后一个点坐标 - 排序后第一个点坐标（对应k=1的极端场景）
• 每次取区间中间值mid作为候选L，判断该L是否可以用不超过k个线段覆盖所有点
• 若可行则尝试缩小右边界找更小的L，若不可行则扩大左边界找更大的L

3. 贪心策略验证可行性（单次验证时间复杂度O(n)） #

遍历排序后的点，用贪心逻辑计算覆盖需要的最少线段数：

1. 初始化已使用线段数为1，当前线段的右端点为排序后第一个点坐标 + 候选L
2. 依次遍历后续每个点：如果当前点坐标超过当前线段的右端点，就新增一个线段，将新线段的右端点更新为当前点坐标 + 候选L，同时线段数+1
3. 遍历结束后如果总线段数<=k，则当前候选L可行，否则不可行

贪心策略正确性证明：要覆盖当前未被覆盖的最左侧点，把线段左端点放在该点的位置，能覆盖最多的右侧点，是所有可行放法中的最优选择，不会得到比最优解更多的线段数。

时间复杂度验证 #

排序阶段为O(nlogn)，由于坐标范围为[0, n³]，二分总次数为log₂(n³) = 3logn，每次可行性验证为O(n)，总时间复杂度为O(nlogn + 3nlogn) = O(nlogn)，符合要求。

内容的提问来源于stack exchange，提问作者Sakura