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

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]

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

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

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

Xor(^) по существу переводит busy_hours в not_busy_hours.Добавление (&) 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 минут в данном примере) на каждой итерации.Если временной интервал доступен, он добавляется к началу допустимого времени.Таким образом, когда процесс завершается, acceptable_times сортируется в порядке появления.

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

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

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

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

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