如何查找范围是否包含在范围数组中？ [英] How to find if range is contained in an array of ranges?

问题描述

示例

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

...

然后我会有一堆事件占用这些时间间隔，例如

I then have a bunch of events which occupy some of these intervals, for example

event = { start_at: somedatetime, end_at: somedatetime }

某个日期到某个日期，我创建另一个数组

Iterating over events from a certain date to a certain date, I create another array

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'] = 900，845..915，900..930，等等]

不是以15分钟为单位检查available_hours

Not that it checks available_hours in increments of 15 minutes for slots of specified duration.

感谢您的帮助！

推荐答案

认为这是一个位字段的工作。不幸的是，这个解决方案将依赖于幻数，转换辅助和一个公平的二进制逻辑，所以它不会漂亮。但它会工作和非常高效。

I think this is a job for bit fields. Unfortunately this solution will rely on magic numbers, conversions helpers and a fair bit of binary logic, so it won't be pretty. But it will work and be very efficient.

这是我如何处理这个问题：

This is how I'd approach the problem:

以合理的时间间隔将你的日子雾化。我会按照你的例子，把每个15分钟的时间段视为一次性块（主要是因为它保持简单的例子）。然后用十六进制数表示每小时的可用性。

Atomize your days into reasonable time intervals. I'll follow your example and treat each 15 minute block of time as considered one time chunk (mostly because it keeps the example simple). Then represent your availability per hour as a hex digit.

示例：

• 0xF = 0x1111 =>


• 0xC = 0x1100 =>可用于上半小时。

这些字符串中的24个一起表示一天。或更少，如果你可以确保没有事件将发生超出范围。示例继续假设24小时。

String 24 of these together together to represent a day. Or fewer if you can be sure that no events will occur outside of the range. The example continues assuming 24 hours.

从这一点上，我已经把长十六进制数字拆分为单词，以便于阅读。
假设一天从00:00到23:59 business_hours ['monday'] = 0x0000 0000 FFFF 0FFF F000 0000

From this point on I've split long Hex numbers into words for legibility Assuming the day goes from 00:00 to 23:59 business_hours['monday'] = 0x0000 0000 FFFF 0FFF F000 0000

以类似的格式，只是&

To get busy_hours you store events in a similar format, and just & them all together.

示例：

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可以得到可用时间：

From busy_hours and business_hours you can get available hours:

available_hours = business_hours& （busy_hours ^ 0xFFFF FFFF FFFF FFFF FFFF FFFF）

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给我们一天的可用时间。

The xor(^) essentialy translates busy_hours into not_busy_hours. Anding (&) not_busy_hours with business_hours gives us the available times for the day.

此计划也可以方便地比较许多人的可用时间。

This scheme also makes it simple to compare available hours for many people.

all_available_hours = person_a_available_hours & person_b_available_hours & person_c_available_hours

然后找到适合小时的时间段。你需要做这样的事情：
将你的时间长度转换成一个类似的十六进制数字到一个小时，其中的代表时间段将覆盖的那个小时的所有时间块。

Then to find a time slot that fits into available hours. You need to do something like this: Convert your length of time into a similar hex digit to the an hour where the ones represent all time chunks of that hour the time slot will cover. Next right shift the digit so there's no trailing 0's.

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

Examples are better than explanations: 0x1 => 15 minutes, 0x3 => half hour, 0x7 => 45 minutes, 0xF => full hour, ... 0xFF => 2 hours, etc.

一旦你这样做了：

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

范围的高端有点乱。所以让我们再看一下。我们不想移动太多次，否则我们可能在频谱的早期端开始得到假阳性。

The high end of the range is a bit of a mess. So lets look a bit more at it. We don't want to shift too many times or else we'll could start getting false positives at the early end of the spectrum.

24 * 4 一天24小时，每个由4位表示。
- （＃时隙中的时间块的时间）在我们正在寻找的时间段每15分钟减去1检查。该值可以通过（Math.log（time_slot_in_hex）/Math.log（2））找到。floor + 1

24 * 4 24 hours in the day, with each represented by 4 bits. - (#of time chunks in time slot) Subtract 1 check for each 15 minutes in the time slot we're looking for. This value can be found by (Math.log(time_slot_in_hex)/Math.log(2)).floor + 1

它在每天结束时开始，检查每个时间段，在每次迭代时提前一个时间块（在本例中为15分钟）。如果时隙可用，则将其添加到可接受时间的开始。因此，当过程完成后，可以按照发生的顺序对可接受的时间进行排序。

Which starts at the end of the day, checking each time slot, moving earlier by a time chunk (15 minutes in this example) on each iteration. If the time slot is available it's added to the start of acceptable times. So when the process finishes acceptable_times is sorted in order of occurrence.

很酷的是，此实现允许包含时间段，

The cool thing is this implementation allows for time slots that incorporate so that your attendee can have a busy period in their day that bisects the time slot you're looking for with a break, where they might be otherwise busy.

这是由你来编写帮助函数，它可以在一个时间段之间转换，范围数组（即：[800..1200，1300..1700]）和十六进制表示。最好的方法是将行为封装在对象中，并使用自定义访问器方法。然后使用相同的对象来表示天，事件，繁忙时间等。这个方案中没有内置的唯一的事情是如何安排事件，以便他们可以跨越天的边界。

It's up to you to write helper functions that translate between an array of ranges (ie: [800..1200, 1300..1700]) and the hex representation. The best way to do that is to encapsulate the behaviour in an object and use custom accessor methods. And then use the same objects to represent days, events, busy hours, etc. The only thing that's not built into this scheme is how to schedule events so that they can span the boundary of days.

这篇关于如何查找范围是否包含在范围数组中？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！