4

假设我想在 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 )，将其除以二并四舍五入。

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

4

4 回答 4

2

由于您最多只能安排 60 个事件，所以我认为使用静态表值得一试（与思考算法和测试相比）。我的意思是对你来说，在时间之内安排事件是非常微不足道的任务。但是告诉计算机如何做到这一点并不容易。

所以，我建议用静态时间值来定义表，在该表中放置下一个事件。它可能是这样的：

00:00, 01:00, 00:30, 00:15, 00:45...
于 2012-08-01T13:59:36.563 回答
2

您可以使用位反转来安排您的活动。只需采用事件序列号的二进制表示，反转其位，然后将结果缩放到给定范围（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

按顺序生成位反转字的方法是从“计算事项 ”第 1.14.3 章借用的。

更新：

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

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

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

至

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

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

其他算法

前面的方法很简单，但它只能保证（在任何时候）最大的空槽不超过最小槽的两倍。由于您希望将事件尽可能分开，因此基于斐波那契数或黄金比例的算法可能是首选：

  1. 将初始间隔 (0..59) 放入优先级队列（最大堆，优先级 = 间隔大小）。
  2. 要安排一个事件，弹出优先级队列，以黄金比例 (1.618) 分割生成的间隔，使用分割点作为该事件的时间，并将两个生成的间隔放回优先级队列。

这保证了最大的空槽不超过（大约）最小槽的 1.618 倍。对于较小的插槽，近似值会变差，并且尺寸与 2:1 相关。

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

于 2012-08-01T14:13:53.073 回答
1

由于您无法重新安排活动，并且您不提前知道有多少活动将到达，我怀疑您自己的建议（带有 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 分钟
于 2012-08-01T13:56:48.893 回答
0

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

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

each_cons(2) 得到二元组；其余的可能很简单：

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
于 2012-08-01T14:08:45.637 回答