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