Как узнать, содержится ли диапазон в массиве диапазонов?

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

available_hours = business_hours - busy_hours

• Учитывая определенную продолжительность, скажем, 30 минут, найдите, какие временные интервалы доступны в available_hours. В приведенных выше примерах такой метод вернул бы

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

Не то, чтобы он проверял доступные_часы с шагом 15 минут для слотов указанной длительности.

Спасибо за помощь!

Answer 1

Я думаю, что это работа для битовых полей. К сожалению, это решение будет опираться на магические числа, помощники по преобразованию и немного бинарной логики, поэтому оно не будет красивым. Но это будет работать и будет очень эффективно.

Вот как я подхожу к проблеме:

Распыляйте свои дни на разумные промежутки времени. Я последую вашему примеру и буду рассматривать каждый 15-минутный отрезок времени как один раз (в основном потому, что пример прост). Затем представьте свою доступность за час в виде шестнадцатеричной цифры.

Пример:

• 0xF = 0x1111 => доступно на весь час.
• 0xC = 0x1100 => доступно в течение первой половины часа.

Строка 24 из них вместе, чтобы представить день. Или меньше, если вы можете быть уверены, что за пределами диапазона не произойдет никаких событий. В примере продолжается 24 часа.

С этого момента я разбил длинные шестнадцатеричные числа на слова для удобства чтения. Предполагая, что день идет с 00:00 до 23:59 business_hours['monday'] = 0x0000 0000 FFFF 0FFF F000 0000

Для того, чтобы занять часы, вы сохраняете события в аналогичном формате, и просто & все вместе.

Пример:

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 

Из часов занятости и рабочих часов вы можете получить доступные часы:

available_hours = business_hours & (busy_hours ^ 0xFFFF FFFF FFFF FFFF FFFF FFFF)

xor (^) существенно переводит busy_hours в not_busy_hours. Anding (&) not_busy_hours с business_hours дает нам доступное время для дня.

Эта схема также упрощает сравнение доступных часов для многих людей.

all_available_hours = person_a_available_hours & person_b_available_hours & person_c_available_hours

Затем найдите временной интервал, который соответствует доступным часам. Вам нужно сделать что-то вроде этого: Преобразуйте ваш отрезок времени в аналогичную шестнадцатеричную цифру в час, где единица представляет все отрезки времени того часа, который охватит временной интервал. Затем сдвиньте цифру вправо, чтобы не было завершающих нулей.

Примеры лучше объяснений: 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) Вычтите 1 чек за каждые 15 минут в искомом интервале времени. Это значение можно найти по (Math.log(time_slot_in_hex)/Math.log(2)).floor + 1

Который начинается в конце дня, проверяя каждый временной интервал, перемещаясь раньше на временной отрезок (в этом примере 15 минут) на каждой итерации. Если временной интервал доступен, он добавляется к началу приемлемого времени. Поэтому, когда процесс завершается, значение visible_times сортируется в порядке появления.

Круто то, что эта реализация учитывает временные интервалы, которые включают в себя, так что у вашего участника может быть занятой период в их день, который делит временной интервал, который вы ищете, с перерывом, где они могут быть заняты в противном случае.

Вы должны написать вспомогательные функции, которые преобразуются между массивом диапазонов (то есть: [800..1200, 1300..1700]) и шестнадцатеричным представлением. Лучший способ сделать это - инкапсулировать поведение в объекте и использовать собственные методы доступа. А затем используйте те же объекты для представления дней, событий, часов работы и т. Д. Единственное, что не встроено в эту схему, - это как запланировать события, чтобы они могли охватывать границы дней.

Answer 2

Хорошо, у меня нет времени, чтобы написать полное решение, но проблема не кажется мне слишком сложной. Я взломал вместе следующие примитивные методы, которые вы можете использовать, чтобы помочь в построении вашего решения (вы можете захотеть создать подкласс 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

Это должен быть подход многократного использования. Конечно, вам понадобится что-то совершенно другое для следующей части вашего вопроса, но это все, на что у меня есть время:)

Answer 3

Чтобы ответить на заголовок вашего вопроса, найдите, если диапазон массивов содержит диапазон:

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