找到周期中最大空闲时隙中间的算法？

Question

假设我想在 00:00–00:59 期间安排一系列事件。我将它们安排在整分钟(00:01，从不在 00:01:30)。

我想在这段时间内尽可能将它们隔开，但我事先不知道在那一小时内我总共会有多少事件。我可能会在今天安排一场事件，明天再安排两场。

我脑子里有一个明显的算法，我可以想出强力的方法来实现它，但我相信有人知道更好的方法。我更喜欢 Ruby 或我可以翻译成 Ruby 的东西，但我会尽我所能。

所以我脑子里能想到的算法:

事件 1 刚好在 00:00 结束。

事件 2 在 00:30 结束，因为该时间距现有事件最远。

事件 3 可能会在 00:15 或 00:45 结束。所以也许我只选择第一个，00:15。

然后事件 4 在 00:45 结束。

事件 5 在 00:08 左右结束(从 00:07:30 向上舍入)。

等等。

所以我们可以查看每一对记录的分钟数(例如，00:00–00:15、00:15–00:30、00:30–00:00)，选择最大的范围 (00:30– 00:00)，将其除以二并取整。

但我相信它可以做得更好。分享!

Answer 1

您可以使用位反转来安排您的事件。只需采用事件序列号的二进制表示，反转其位，然后将结果缩放到给定范围(0..59 分钟)。

另一种方法是按顺序 (0000,1000,0100,1100,...) 生成位反转字。

这允许轻松分发多达 32 个事件。如果需要更多事件，在缩放结果后，您应该检查结果分钟是否已被占用，如果已占用，则生成并缩放下一个单词。

这是 Ruby 中的示例:

class Scheduler
  def initialize
    @word = 0
  end

  def next_slot
    bit = 32
    while  (((@word ^= bit) & bit) == 0) do
      bit >>= 1;
    end
  end

  def schedule
    (@word * 60) / 64
  end
end


scheduler = Scheduler.new

20.times do
  p scheduler.schedule
  scheduler.next_slot
end

顺序生成位反转字的方法借鉴自“Matters Computational”，第1.14.3章。

---

更新:

由于从 0..63 缩放到 0..59，该算法倾向于在 0、15、30 和 45 之后生成最小的槽。问题是:它总是从这些(最小的)槽开始填充间隔，而从最大的插槽开始填充更自然。因此，算法并不完美。额外的问题是需要检查“已占用分钟数”。

幸运的是，一个小的修复解决了所有这些问题。只是改变

while  (((@word ^= bit) & bit) == 0) do

到

while  (((@word ^= bit) & bit) != 0) do

并用 63 初始化 @word(或者继续用 0 初始化它，但进行一次迭代以获得第一个事件)。此修复将反向字从 63 减少到零，它始终将事件分发到最大可能的槽，并且在前 60 次迭代中不允许出现“冲突”事件。

---

其他算法

以前的方法很简单，但它只能保证(在任何时刻)最大的空槽不超过最小槽的两倍。由于您希望将事件间隔得尽可能远，因此可能首选基于斐波那契数或黄金比例的算法:

1. 将初始区间 (0..59) 放入优先级队列(最大堆，优先级 = 区间大小)。
2. 要安排一个事件，弹出优先级队列，按黄金比例 (1.618) 拆分结果间隔，使用拆分点作为此事件的时间，并将两个结果间隔放回优先级队列。

这保证了最大的空槽不超过(大约)最小槽的 1.618 倍。对于较小的插槽，近似值会变差，大小相关为 2:1。

如果在调度更改之间保持优先级队列不方便，您可以提前准备一个包含 60 个可能事件的数组，并在每次需要新事件时从该数组中提取下一个值。