如何查找范围数组中是否包含范围？

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]

...

现在我的挑战是

• 创建包含business_hours减去busy_hours的available_hours数组

available_hours = business_hours - busy_hours

• 给定持续时间30分钟,找出available_hours中可用的时隙.在上面的例子中,这种方法将返回

available_slots['monday'] = [830..900, 845..915, 900..930, and so on]

并非它为指定持续时间的插槽以15分钟为增量检查available_hours.

谢谢您的帮助!

Answer 1

我认为这是比特领域的工作.不幸的是,这个解决方案将依赖于幻数,转换助手和相当多的二进制逻辑,所以它不会很漂亮.但它会起作用并且效率很高.

这就是我解决问题的方法:

将您的日子雾化为合理的时间间隔.我将按照你的例子,将每个15分钟的时间块视为一次性块(主要是因为它使示例变得简单).然后将每小时的可用性表示为十六进制数字.

例:

• 0xF = 0x1111 =>可用于整个小时.
• 0xC = 0x1100 =>可用于前半个小时.

这些字符串24一起代表一天.如果您可以确定在该范围之外不会发生任何事件,则会更少.这个例子假设24小时.

从这一点开始,我将长十六进制数字分成单词以便于读取假设当天从00:00到23:59 business_hours['monday'] = 0x0000 0000 FFFF 0FFF F000 0000

为了获得busy_hours,您可以以类似的格式存储事件,并将它们全部放在一起.

Exmample:

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 ^ 0xFFFF FFFF FFFF FFFF FFFF FFFF)

xor(^)essentialy将busy_hours转换为not_busy_hours.Anding(&)not_busy_hours with business_hours为我们提供了当天的可用时间.

该方案还使得比较许多人的可用时间变得简单.

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分钟减去1次检查.该值可以通过以下方式找到(Math.log(time_slot_in_hex)/Math.log(2)).floor + 1

从一天结束时开始,检查每个时间段,在每次迭代时提前移动一个时间块(在此示例中为15分钟).如果时隙可用,则将其添加到可接受时间的开始.因此,当进程完成时,accepted_times按发生顺序排序.

很酷的是这个实现允许合并的时间段,以便您的与会者可以在一天中有一个忙碌的时间段,将您正在寻找的时间段分成两半,在那里他们可能会很忙.

您可以编写辅助函数,在一系列范围(即:[800..1200,1300..1700])和十六进制表示之间进行转换.最好的方法是将行为封装在对象中并使用自定义访问器方法.然后使用相同的对象来表示日期,事件,繁忙时间等.此方案中没有内置的唯一事情是如何安排事件以便它们可以跨越天的边界.