Comment trouver si la plage est contenue dans un tableau de plages?

Question

Exemple

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

...

je alors un tas d'événements qui occupent certains de ces intervalles, par exemple

event = { start_at: somedatetime, end_at: somedatetime } 

Enumérer les événements d'une certaine date à un certain date, je crée un autre tableau

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

...

Maintenant, mes défis sont

• Création d'un tableau available_hours qui contient Business_hours moins busy_hours

available_hours = business_hours - busy_hours

• donné une certaine durée dire 30 minutes, trouver que le temps Les slots sont disponibles dans available_hours. Dans les exemples ci-dessus, une telle méthode retournerait

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

Non qu'il vérifie available_hours par incréments de 15 minutes pour les fentes de durée déterminée.

Merci pour l'aide!

Answer 1

Je pense que c'est un travail pour les champs de bits. Malheureusement, cette solution reposera sur des nombres magiques, des aides à la conversion et une bonne partie de la logique binaire, donc ce ne sera pas joli. Mais cela fonctionnera et sera très efficace.

Voici comment j'aborder le problème:

Anéantissez vos jours dans des intervalles de temps raisonnables. Je vais suivre votre exemple et traiter chaque bloc de temps de 15 minutes comme étant considéré comme un morceau de temps (surtout parce qu'il garde l'exemple simple). Ensuite, représentez votre disponibilité par heure en tant que chiffre hexadécimal.

Exemple:

• 0xF = 0x1111 => disponible pour toute heure.
• 0xC = 0x1100 => disponible pour la première moitié de l'heure.

Chaîne de 24 ensemble pour représenter un jour. Ou moins si vous pouvez être sûr qu'aucun événement ne se produira en dehors de la plage. L'exemple continue en supposant 24 heures.

A partir de là, j'ai Fractionnement des nombres hexadécimaux en mots pour la lisibilité En supposant que le jour va 0h00-à-23h59 business_hours['monday'] = 0x0000 0000 FFFF 0FFF F000 0000

Pour busy_hours vous stocker des événements dans un format similaire, et juste & tous ensemble.

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 

De busy_hours et Business_hours vous pouvez obtenir des heures disponibles:

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

XOR (^) essentialy traduit busy_hours en not_busy_hours. Anding (&) not_busy_hours avec business_hours nous donne les heures disponibles pour la journée.

Ce système facilite également la comparaison des heures disponibles pour de nombreuses personnes.

all_available_hours = person_a_available_hours & person_b_available_hours & person_c_available_hours 

Puis de trouver un intervalle de temps qui correspond aux heures disponibles. Vous devez faire quelque chose comme ceci: Convertissez votre longueur de temps en un chiffre hexadécimal similaire à l'heure où les uns représentent tous les morceaux de temps de cette heure que l'intervalle de temps couvrira. Ensuite, déplacez le chiffre vers la droite pour qu'il n'y ait pas de 0 à la fin.

exemples sont mieux que des explications: 0x1 => 15 minutes, 0x3 => demi-heure, 0x7 => 45 minutes, 0xF => pleine heure, ... 0xFF => 2 heures, etc.

Une fois que vous avez fait cela, vous faites ceci:

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 

Le haut de gamme est un peu en désordre. Alors regardons un peu plus là-dessus. Nous ne voulons pas changer trop souvent, sinon nous pourrions commencer à obtenir des faux positifs au tout début du spectre.

24 * 4 24 heures dans la journée, chacune représentée par 4 bits. Soustrayez 1 chèque toutes les 15 minutes dans le créneau horaire que nous recherchons.Cette valeur peut être trouvée par (Math.log(time_slot_in_hex)/Math.log(2)).floor + 1

Qui commence à la fin de la journée, en vérifiant chaque intervalle de temps, se déplaçant plus tôt par un morceau de temps (15 minutes dans cet exemple) à chaque itération. Si le créneau horaire est disponible, il est ajouté au début des heures acceptables. Ainsi, lorsque le processus termine acceptable_times est trié par ordre d'occurrence. Ce qui est cool, c'est que cette implémentation permet aux créneaux horaires qui intègrent pour que votre participant puisse avoir une période occupée dans leur journée qui divise l'intervalle de temps que vous cherchez avec une pause, où ils pourraient être autrement occupés. C'est à vous d'écrire des fonctions d'aide qui se traduisent par un tableau de plages (ie: [800..1200, 1300..1700]) et la représentation hexadécimale. Le meilleur moyen d'y parvenir est d'encapsuler le comportement dans un objet et d'utiliser des méthodes d'accès personnalisées. Ensuite, utilisez les mêmes objets pour représenter les jours, les événements, les heures de pointe, etc. La seule chose qui n'est pas intégrée dans ce schéma est la façon de planifier les événements afin qu'ils puissent s'étendre sur plusieurs jours.

Answer 2

Pour répondre à titre de votre question, trouver si une gamme de tableaux contient une gamme:

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 

qui pourrait être écrit

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

Answer 3

D'accord, je n'ai pas le temps d'écrire une solution complète, mais le problème ne me semble pas trop difficile. Je piraté ensemble les méthodes primitives suivantes que vous pouvez utiliser pour aider à la construction de votre solution (Vous voudrez peut-être sous-classe Range plutôt que rapiéçage de singe, mais cela vous donnera l'idée):

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 

Vous pouvez parcourir les heures d'ouverture et trouver celui qui contient l'événement comme ceci:

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

Vous pouvez construire le nouveau tableau comme celui-ci (pseudocode, non testé):

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

cela devrait être une jolie approche réutilisable. Bien sûr, vous aurez besoin de quelque chose de totalement différent pour la prochaine partie de votre question, mais c'est tout ce que j'ai le temps pour :)