假设我有一个循环时间轴(24 小时周期)，在这 24 小时内有 n 个点。我想用给定的固定长度 k (<24h) 的间隔覆盖所有点，并且我想使用尽可能少的间隔。有没有好的算法来确定最佳区间的起点？
如果我们不允许区间“环绕”那么它就变得容易了(我们可以简单地贪婪地安排第一个区间从第一个点开始，覆盖尽可能多的点并为下一个区间选择下一个点等)。
一个天真的二次解决方案是尝试将每个点作为“第一个”区间的起点并按照上面的方法做，但我觉得我们可以做一些更聪明的事情？
最佳答案
请注意您建议的朴素二次解:您需要将每个点视为区间开始或区间结束。
我不确定这是最优解，但它比朴素的二次方更好:
让我们命名这些点 {P1, ..., Pn}。
由于任何点必须被至少一个区间覆盖，找到可能覆盖点 P1 的所有区间(假设一个区间要么从 Pi 开始，要么结束于 Pi).对于这些间隔中的每一个，贪婪地继续，就像在线性时间线上一样。
要进一步优化它，而不是从 P1 开始，我们需要找到最佳起点 - 这将是可能被最少数量的间隔覆盖的点。我不知道我们是否可以在线性时间内做到这一点，但一个好的启发式方法可能是从它到它的两个邻居的距离之和最大这一点开始。
编辑:寻找最佳起点的 O(nlogn) 方法:
我们可以构建一个可能的 2n 段列表(对于任何点 Pi，间隔可以从 Pi 开始或结束于 Pi).接下来，将这些间隔插入 segment tree .
不使用常规线段树，而是不将间隔存储在规范子集中，而是简单地存储它们的数量(参见维基百科文章中的注释部分)。
树的构建需要 O(nlogn) 的时间。现在，对于每个点 Pi，计算它落入的段数(区间)。每个点需要 O(logn)，或者总共需要 O(nlogn)。
选择间隔数最少的点。对于每个间隔，继续使用贪心方法，如上所述。
关于algorithm - 固定长度的圆形聚类，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17282684/