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

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–0:00），将其除以2并取整。

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

Answer 1

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

另一种选择是按顺序生成位反转字（0000100001001100，…）。

这允许轻松分发多达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个可能的事件组成的数组，并在每次需要新事件时从该数组中提取下一个值。

Answer 2

由于最多只能安排60个事件，因此我认为使用静态表值得一试（与思考算法和测试算法相比）。我的意思是，对您来说，在时间内安排事件是一项非常琐碎的任务。但要告诉计算机如何做这件事并不是那么容易。

所以，我建议用静态的时间值来定义表，以便放置下一个事件。它可能类似于：

00:00, 01:00, 00:30, 00:15, 00:45...

Answer 3

由于您无法重新安排活动，也不知道会有多少活动提前到达，我怀疑您自己的建议（Roman注意使用01:00）是最好的。

然而，如果你对最大到达的事件数量有任何估计，你可能会对其进行优化。例如，假设你估计最多7个事件，你可以准备60 / (n - 1)=10分钟的时段，并像这样安排事件：

• 00:00
• 01:00
• 00:30
• 00:10
• 00:40
• 00:20
• 00:50//10分钟

请注意，最后几个事件可能不会到达，因此使用00:50的概率很低。

这将比基于非估计的算法更公平，尤其是在使用所有时隙的最坏情况下：

• 00:00
• 01:00
• 00:30
• 00:15
• 00:45
• 00:07
• 00:37//仅相隔7分钟

Answer 4

我为我的解决方案编写了一个Ruby实现。它的边缘情况是，任何超过60的事件都将在0分钟堆积起来，因为现在每个空闲时间空间都是相同的大小，它更喜欢第一个。

我没有具体说明如何处理超过60的事件，我也不在乎，但我想如果你在乎的话，随机化或循环可以解决这种边缘情况。

CCD_ 3得到bigram；剩下的可能很简单：

class Scheduler
  def initialize
    @scheduled_minutes = []
  end
  def next_slot
    if @scheduled_minutes.empty?
      slot = 0
    else
      circle = @scheduled_minutes + [@scheduled_minutes.first + 60]
      slot = 0
      largest_known_distance = 0
      circle.each_cons(2) do |(from, unto)|
        distance = (from - unto).abs
        if distance > largest_known_distance
          largest_known_distance = distance
          slot = (from + distance/2) % 60
        end
      end
    end
    @scheduled_minutes << slot
    @scheduled_minutes.sort!
    slot
  end
  def schedule
    @scheduled_minutes
  end
end

scheduler = Scheduler.new
20.times do
  scheduler.next_slot
  p scheduler.schedule
end