effiziente Möglichkeit, den Unterschied einer Periode und Satz von Bereichen in Ruby zu finden

Question

ich einige Zeit habe reicht in Ruby:

period = Time.parse('8:00am')..Time.parse('8:00pm') 
incidents = [ 
    Time.parse('7:00am')..Time.parse('9:00am'), 
    Time.parse('1:00pm')..Time.parse('3:00pm'), 
    Time.parse('1:30pm')..Time.parse('3:30pm'), 
    Time.parse('7:00pm')..Time.parse('9:00pm'), 
] 

Ich versuche, eine Reihe von einfallenden freien Blöcken zu bekommen innerhalb die Periode. Für die oben, dass sein würde:

[ 
    Time.parse('9:00am')..Time.parse('1:00pm') 
    Time.parse('3:30pm')..Time.parse('7:00pm') 
] 

Aus dem Vorstehenden ist es möglich, Vorfälle außerhalb des Zeitraums zu überlappen oder zu erweitern. Gibt es irgendwelche Operationen für die Entfernung oder ähnliches, die diese Art der Berechnung vereinfachen würden?

Answer 1

Let full_range ein Bereich sein und ranges ein Array von Bereichen liegen, repräsentieren, was die Fragesteller period und incidents bezeichnet ist. Ich habe angenommen, dass die in allen Bereichen enthaltenen Elemente beliebige Objekte sein können, vorausgesetzt, sie können mit der Methode der anwendbaren Klasse <=> verglichen werden und das Modul Comparable wurde include d.

-Code

def uncovered_ranges(full_range, ranges) 
    ucrs = [full_range] 
    ranges.each do |r| 
    ucrs = ucrs.flat_map do |ucr| 
     if ucr.first >= r.last || ucr.last <= r.first 
     ucr 
     elsif r.first <= ucr.first && r.last >= ucr.last 
     nil 
     elsif r.first <= ucr.first && r.last < ucr.last 
     r.last..ucr.last 
     elsif r.first > ucr.first && r.last >= ucr.last 
     ucr.first..r.first 
     else 
     [ucr.first..r.first, r.last..ucr.last] 
     end 
    end.compact 
    end 
    ucrs 
end 

Beispiele

full_range = 1..20 
ranges = [3..4, 6..8, 10..12, 8..14, 16..17, 20..20] 

uncovered_ranges(full_range, ranges) 
    #=> [1..3, 4..6, 14..16, 17..20] 

require 'time' 

full_range = Time.parse('8:00am')..Time.parse('8:00pm') 
    #=> 2016-12-22 08:00:00 -0800..2016-12-22 20:00:00 -0800 

ranges = [ 
    Time.parse('7:00am')..Time.parse('9:00am'), 
    Time.parse('1:00pm')..Time.parse('3:00pm'), 
    Time.parse('1:30pm')..Time.parse('3:30pm'), 
    Time.parse('7:00pm')..Time.parse('9:00pm'), 
] 
    #=> [2016-12-22 07:00:00 -0800..2016-12-22 09:00:00 -0800, 
    # 2016-12-22 13:00:00 -0800..2016-12-22 15:00:00 -0800, 
    # 2016-12-22 13:30:00 -0800..2016-12-22 15:30:00 -0800, 
    # 2016-12-22 19:00:00 -0800..2016-12-22 21:00:00 -0800] 

uncovered_ranges(full_range, ranges) 
    #=> [2016-12-22 09:00:00 -0800..2016-12-22 13:00:00 -0800, 
    # 2016-12-22 15:30:00 -0800..2016-12-22 19:00:00 -0800] 

Erklärung

Vielleicht ist die einfachste und durch Weg für mich zu erklären, was los ist einige puts einfügen Anweisungen und führen Sie den Code für das erste Beispiel oben aus.

def uncovered_ranges(full_range, ranges) 
    ucrs = [full_range] 
    puts "ucrs initially=#{ucrs}" 
    ranges.each do |r| 
    puts "\ncovering range r=#{r}" 
    ucrs = ucrs.flat_map do |ucr| 
     puts " range uncovered so far ucr=#{ucr}" 
     if ucr.first >= r.last || ucr.last <= r.first 
     puts " in if #1, returning #{ucr}" 
     ucr 
     elsif r.first <= ucr.first && r.last >= ucr.last 
     puts " in if #2, returning nil" 
     nil 
     elsif r.first <= ucr.first && r.last < ucr.last 
     puts " in if #3, returning #{r.last..ucr.last}" 
     r.last..ucr.last 
     elsif r.first > ucr.first && r.last >= ucr.last 
     puts " in if #4, returning #{ucr.first..r.first}" 
     ucr.first..r.first 
     else 
     puts " in else, returning #{[ucr.first..r.first, r.last..ucr.last]}" 
     [ucr.first..r.first, r.last..ucr.last] 
     end 
    end.tap { |u| puts "ucrs after processing range #{r}=#{u}" }. 
     compact. 
     tap { |u| puts "ucrs after compact=#{u}" } 
    end 
    ucrs 
end 

uncovered_ranges 1..20, [3..4, 6..8, 10..12, 8..14, 16..17, 20..20] 

druckt Folgendes.

ucrs initially=[1..20] 

covering range r=3..4 
    range uncovered so far ucr=1..20 
    in else, returning [1..3, 4..20] 
ucrs after processing range 3..4=[1..3, 4..20] 
ucrs after compact=[1..3, 4..20] 

covering range r=6..8 
    range uncovered so far ucr=1..3 
    in if #1, returning 1..3 
    range uncovered so far ucr=4..20 
    in else, returning [4..6, 8..20] 
ucrs after processing range 6..8=[1..3, 4..6, 8..20] 
ucrs after compact=[1..3, 4..6, 8..20] 

covering range r=10..12 
    range uncovered so far ucr=1..3 
    in if #1, returning 1..3 
    range uncovered so far ucr=4..6 
    in if #1, returning 4..6 
    range uncovered so far ucr=8..20 
    in else, returning [8..10, 12..20] 
ucrs after processing range 10..12=[1..3, 4..6, 8..10, 12..20] 
ucrs after compact=[1..3, 4..6, 8..10, 12..20] 

covering range r=8..14 
    range uncovered so far ucr=1..3 
    in if #1, returning 1..3 
    range uncovered so far ucr=4..6 
    in if #1, returning 4..6 
    range uncovered so far ucr=8..10 
    in if #2, returning nil 
    range uncovered so far ucr=12..20 
    in if #3, returning 14..20 
ucrs after processing range 8..14=[1..3, 4..6, nil, 14..20] 
ucrs after compact=[1..3, 4..6, 14..20] 

covering range r=16..17 
    range uncovered so far ucr=1..3 
    in if #1, returning 1..3 
    range uncovered so far ucr=4..6 
    in if #1, returning 4..6 
    range uncovered so far ucr=14..20 
    in else, returning [14..16, 17..20] 
ucrs after processing range 16..17=[1..3, 4..6, 14..16, 17..20] 
ucrs after compact=[1..3, 4..6, 14..16, 17..20] 

covering range r=20..20 
    range uncovered so far ucr=1..3 
    in if #1, returning 1..3 
    range uncovered so far ucr=4..6 
    in if #1, returning 4..6 
    range uncovered so far ucr=14..16 
    in if #1, returning 14..16 
    range uncovered so far ucr=17..20 
    in if #1, returning 17..20 
ucrs after processing range 20..20=[1..3, 4..6, 14..16, 17..20] 
ucrs after compact=[1..3, 4..6, 14..16, 17..20] 
    #=> [1..3, 4..6, 14..16, 17..20] 

Answer 2

Mögliche Lösung

Mit dieser range operator gem, dieses Skript würde (fast) zurückgeben, was Sie wollen.

Es beginnt mit period und subtrahiert nacheinander alle incident.

Da eine Reihe von einem anderen Substraktion in zwei Bereichen zur Folge haben kann, beginnt das Skript tatsächlich mit [period] und hält eine Reihe von freiem Vorfall im Bereich zwischen Iterationen:

require 'range_operators' 

incident_free = incidents.inject([period]) do |free_ranges, incident| 
    free_ranges.flat_map do |free_range| 
    free_range - incident 
    end 
end 

p incident_free 
#=> [2016-12-22 09:00:01 +0100..2016-12-22 12:59:59 +0100, 2016-12-22 15:30:01 +0100..2016-12-22 18:59:59 +0100] 

Hinweise

Sie wirft Time#succ ist obsolet. Sie können entweder hinzufügen

class Time 
    def succ 
    self+1 
    end 
end 

die deprecation Warnungen entfernen oder eine Gemfile verwenden mit:

gem 'range_operators', :git => 'https://github.com/monocle/range_operators.git' 

eine neuere Version des Edelsteins zu installieren, mit einem Fix für Time.

Das Skript arbeitet mit einer Auflösung von 1 Sekunde, und der erste Bereich beginnt bei 09:00:01, da ein Vorfall bis 09:00:00 aufgetreten ist.