Como encontrar se o intervalo está contido em uma variedade de faixas?

Question

Exemplo

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

...

Eu então tenho um monte de eventos que ocupam alguns desses intervalos, por exemplo

event = { start_at: somedatetime, end_at: somedatetime }

Iterando os eventos de uma determinada data para uma determinada data, eu crio outra matriz

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

...

Agora meus desafios são

• Criando uma matriz disponível_hours que contém negócios_hours menos ocupado_hours

available_hours = business_hours - busy_hours

• Dada uma certa duração, digamos 30 minutos, encontre quais horários estão disponíveis em HOURS disponíveis. Nos exemplos acima, esse método retornaria

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

Não que ele verifique disponíveis_hours em incrementos de 15 minutos para slots de duração especificada.

Obrigado pela ajuda!

Answer 1

Eu acho que este é um trabalho para campos de bits. Infelizmente, essa solução dependerá de números mágicos, ajudantes de conversões e uma boa lógica binária, para que não seja bonita. Mas funcionará e será muito eficiente.

É assim que eu abordaria o problema:

Atomize seus dias em intervalos de tempo razoáveis. Seguirei seu exemplo e tratarei cada bloco de tempo de 15 minutos como considerado uma vez (principalmente porque mantém o exemplo simples). Em seguida, represente sua disponibilidade por hora como um dígito hexadecimal.

Exemplo:

• 0xf = 0x1111 => disponível para toda a hora.
• 0xc = 0x1100 => disponível para a primeira metade da hora.

String 24 deles juntos para representar um dia. Ou menos se você puder ter certeza de que nenhum evento ocorrerá fora do intervalo. O exemplo continua assumindo 24 horas.

A partir deste ponto, dividi longos números hexadecimais em palavras para legibilidade, assumindo que o dia vai de 00:00 a 23:59 business_hours['monday'] = 0x0000 0000 FFFF 0FFF F000 0000

Para ficar ocupado_hours, você armazena eventos em um formato semelhante, e justo e todos juntos.

AMMAMENTO:

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 

De Busy_Hours e Business_Hours, você pode obter o horário disponível:

disponível

O XOR (^) traduz essencialmente ocupado_hours em não_busy_hours. Anding (&) NOT_BUSY_HOURS com Business_Hours nos dá os horários disponíveis para o dia.

Esse esquema também simplifica a comparação de horas disponíveis para muitas pessoas.

all_available_hours = person_a_available_hours & person_b_available_hours & person_c_available_hours

Então, para encontrar um horário que se encaixe no horário disponível. Você precisa fazer algo assim: converta seu período de tempo em um dígito hexadecimal semelhante ao A Hour, em que os que representam os pedaços de todos os tempos daquela hora, o horário será cobrir. Em seguida, mude o dígito para que não haja 0 de atrás.

Exemplos são melhores que explicações: 0x1 => 15 minutos, 0x3 => meia hora, 0x7 => 45 minutos, 0xf => hora inteira, ... 0xff => 2 horas, etc.

Depois de fazer isso, você faz isso:

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

O altitude do alcance é um pouco de bagunça. Então, vamos olhar um pouco mais nisso. Não queremos mudar muitas vezes ou poderíamos começar a obter falsos positivos no final do espectro.

24 * 4 24 horas do dia, cada uma representada por 4 bits.- (#of time chunks in time slot) Subtraia 1 Verifique se cada 15 minutos no horário que estamos procurando. Este valor pode ser encontrado por (Math.log(time_slot_in_hex)/Math.log(2)).floor + 1

Que começa no final do dia, verificando cada horário, movendo -se mais cedo por um pedaço de tempo (15 minutos neste exemplo) em cada iteração. Se o horário estiver disponível, ele será adicionado ao início dos horários aceitáveis. Portanto, quando o processo termina aceitável_times é classificado em ordem de ocorrência.

O legal é que essa implementação permite slots de tempo que incorporam para que seu participante possa ter um período movimentado em seus dias, que divide o horário que você está procurando com uma pausa, onde eles poderiam estar ocupados.

Cabe a você escrever funções auxiliares que se traduzem entre uma variedade de faixas (ou seja: [800..1200, 1300..1700]) e a representação hexadecimal. A melhor maneira de fazer isso é encapsular o comportamento em um objeto e usar métodos de acessórios personalizados. E depois use os mesmos objetos para representar dias, eventos, horas ocupadas etc. A única coisa que não está incorporada a esse esquema é como agendar eventos para que eles possam abranger o limite dos dias.

Answer 2

Para responder ao título da sua pergunta, encontre se uma variedade de matrizes contém um intervalo:

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

que poderia ser escrito como

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

Answer 3

Ok, não tenho tempo para escrever uma solução completa, mas o problema não parece muito difícil para mim. Eu invadi os seguintes métodos primitivos que você pode usar para ajudar a construir sua solução (você pode querer subclasse em vez de fazer um patch de macaco, mas isso lhe dará a ideia):

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

Você pode iterar ao longo do horário comercial e encontrar o que contém o evento como assim:

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

Você pode construir a nova matriz como esta (pseudocode, não testada):

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

Essa deve ser uma abordagem bastante reutilizável. Claro que você precisará de algo totalmente diferente para a próxima parte da sua pergunta, mas isso é tudo o que tenho tempo para :)