如何判断一个区间是否包含在一个区间数组中？

Question

示例

business_hours['monday'] = [800..1200, 1300..1700]
business_hours['tuesday'] = [900..1100, 1300..1700]

然后我有一堆事件占据了这些时间段中的一些，例如

event = { start_at: somedatetime, end_at: somedatetime }

从一个特定日期到另一个特定日期遍历事件，我创建另一个数组。

busy_hours['monday'] = [800..830, 1400..1415]

现在我的挑战是：

• 创建一个可用时间数组，其中包含营业时间减去繁忙时间

available_hours = business_hours - busy_hours

• 给定一个特定的持续时间，比如30分钟，找出哪些时间段在可用时间内。在上面的示例中，这样一个方法将返回

available_slots['monday'] = [830..900, 845..915, 900..930, 等等]

请注意，它以15分钟的增量检查可用时间，以获取指定持续时间的时间段。

感谢您的帮助！

- Alexandre

---

这个问题就是为什么调度软件价格昂贵的原因 :) - Kopernik

看起来你可以扩展Range以实现你想要的功能，但问题在于你正在使用基于10的表示法来表示基于60的值。900-830=70，而不是30。 - tadman

@avguchenko 调度的棘手之处在于资源的最优分配。这个问题陈述起来很直接，因为它不涉及任何选择。 - gtd

你可以轻松创建时间范围（尽管我预计日期组件可能会表现得更好）：Time.now..(Time.now + 3600) 或使用 ActiveSupport Time.now..(Time.now + 1.hour)。 - gtd

我认为，如果您在代码内部将一天的时间表示为以15分钟为块的0-95，则可以更轻松地处理生活中的时间。然后，您只需要在显示和输入时将其转换为可读格式。 - glenn mcdonald

Answer 1

我认为这是位域的工作。不幸的是，这个解决方案将依赖于魔术数字、转换帮助程序和相当多的二进制逻辑，所以它不会很漂亮。但它将起作用并且非常有效。

这是我处理问题的方法：

将您的一天分解成合理的时间间隔。我将按照您的示例，将每个15分钟的时间块视为一个时间块（主要是因为它使示例保持简单）。然后，将每小时的可用性表示为十六进制数字。

例如： 0xF = 0x1111 => 整个小时都可以使用。 0xC = 0x1100 => 在第一个半小时内可用。

将24个这样的数字串在一起来表示一天。或者更少，如果您可以确定没有事件会发生在范围之外。以下示例假设为24小时。

从这一点开始，我已将长十六进制数拆分成单词以提高可读性 假设一天从00:00到23:59：business_hours['monday'] = 0x0000 0000 FFFF 0FFF F000 0000 要获得busy_hours，您可以以类似的格式存储事件，并将它们全部&在一起。

例如：

event_a = 0x0000 0000 00F0 0000 0000 0000 # 10:00 - 11:00 
event_b = 0x0000 0000 0000 07F8 0000 0000 # 13:15 - 15:15

busy_hours = event_a & event_b 

从busy_hours和business_hours中，你可以获取可用的时间：

available_hours = business_hours & (busy_hours ^ 0xFFFFFFFFFFFFFFFFFFFF)

xor (^) 实际上将busy_hours翻译为not_busy_hours。使用not_busy_hours与business_hours进行and操作(&)，我们可以得到当天的可用时间。

此方案还使比较多人的可用时间变得简单。

all_available_hours = person_a_available_hours & person_b_available_hours & person_c_available_hours

然后，要找到适合可用时间的时间段。您需要执行以下操作： 将您的时间长度转换为类似于小时的十六进制数字，其中个位数代表该小时的所有时间块，时间段将覆盖这些时间块。接下来，向右移动数字，以便没有尾随的0。

例子胜过解释： 0x1 => 15分钟，0x3 => 半小时，0x7 => 45分钟，0xF => 全小时，... 0xFF => 2小时，等等。

完成此操作后，您需要执行以下操作：

acceptable_times =[]
(0 .. 24 * 4 - (#of time chunks time slot)).each do |i|
  acceptable_times.unshift(time_slot_in_hex) if available_hours & (time_slot_in_hex << i) == time_slot_in_hex << i
end

区间的高端有点混乱，所以我们再详细看看。我们不想进行过多的位移，否则可能会在光谱的早期端出现假阳性。

24 * 4 每天有24小时，每小时由4个比特表示。- (#of time chunks in time slot) 减去我们正在查找的时间段中每15分钟的一个检查。可以通过以下方法找到此值：(Math.log(time_slot_in_hex)/Math.log(2)).floor + 1

从一天的末尾开始，逐个检查每个时间段，每次迭代向前移动一个时间块（在本例中为15分钟）。如果时间段可用，则将其添加到可接受时间的开头。因此，当进程完成时，acceptable_times以发生顺序排序。

很酷的是，此实现允许时间段包含，这样您的参与者就可以在其一天中具有二分您要查找的时间段的繁忙期，并带有休息时间，在此期间他们可能会非常忙碌。

由您编写辅助函数将范围数组（即：[800..1200, 1300..1700]）转换为十六进制表示法。最好的方法是将行为封装在对象中并使用自定义访问器方法。然后使用同一对象表示天、事件、繁忙小时等。此方案中唯一未建立的内容是如何安排事件，以使它们可以跨越天的边界。

- EmFi

---

非常感谢您的帮助。您有汇编语言背景吗？;)那些人喜欢位运算！我将尝试实现这个解决方案。您的电子邮件是多少？如果我成功了，我会回复您的。我还会尝试在Github上共享这个项目。 - Alexandre

没有汇编语言的背景。我只是了解足够的算法二进制逻辑，知道何时有必要降到这样基本的水平。 - EmFi

Answer 2

回答你的问题标题，查找一个数组范围是否包含另一个数组范围：

ary = [800..1200, 1300..1700]

test = 800..830
p ary.any? {|rng| rng.include?(test.first) and rng.include?(test.last)}
# => true

test = 1245..1330
p ary.any? {|rng| rng.include?(test.first) and rng.include?(test.last)}
# => false

这可以被写成

class Range
  def include_range?(r)
    self.include?(r.first) and self.include?(r.last)
  end
end

- glenn jackman

---

如果数组中的范围有重叠，我们必须首先合并。这是我的个人观点。https://dev59.com/IHM_5IYBdhLWcg3wyWSt#1249209 - pierrotlefou

Answer 3

好的，我没有时间写出完整的解决方案，但这个问题对我来说似乎并不太困难。我拼凑了以下原始方法，你可以用它们来帮助构建你的解决方案（你可能想要子类化Range而不是猴子补丁，但这会给你一个想法）：

class Range
  def contains(range)
    first <= range.first || last >= range.last
  end

  def -(range)
    out = []
    unless range.first <= first && range.last >= last
      out << Range.new(first, range.first) if range.first > first
      out << Range.new(range.last, last) if range.last < last
    end
    out
  end
end

您可以遍历营业时间并找到包含事件的那个时间段，如下所示：

event_range = event.start_time..event.end_time
matching_range = business_hours.find{|r| r.contains(event_range)}    

您可以像这样构建新数组（伪代码，未经测试）：

available_hours = business_hours.dup
available_hours.delete(matching_range)
available_hours += matching_range - event_range

这应该是一个非常可重用的方法。当然，你需要完全不同的东西来回答你问题的下一部分，但这就是我现在能提供的时间 :)

- gtd

---

嗨，dasil003。感谢回复。那些Range方法看起来很棒。我会把它们放进我的标准库。确实，第二部分有点棘手。不过看看EmFi的解决方案吧。真的很出色。 - Alexandre

Range.contains 不像你想的那样工作。那个 || 应该是 &&。 - EmFi