efektywny sposób sprawdzić różnicę okresu i ustawić zakresów w Ruby

Question

Mam wiele czasu waha się w 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'), 
] 

Próbuję uzyskać tablicę padających wolnych bloków w okres. Dla powyższego wynika, że ​​byłoby:

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

Z powyższego możliwe jest incydenty się pokrywać lub przedłużyć poza okresem. Czy istnieją jakieś operacje w zasięgu lub coś podobnego, co uprościłoby tego rodzaju obliczenia?

Answer 1

Let full_range być zakres i ranges być tablicą zakresów, reprezentujących co pytający określany period i incidents odpowiednio. Przyjąłem, że elementy zawarte we wszystkich zakresach mogą być dowolnymi obiektami, pod warunkiem, że można je porównać z odpowiednią klasą "metoda <=> i że moduł Comparable został 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 

Przykłady

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] 

Wyjaśnienie

Być może najprostszym i najbardziej przez sposób dla mnie, aby wyjaśnić, co się dzieje jest wstawienie niektórych puts i uruchom kod dla pierwszego przykładu powyżej.

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] 

drukuje następujące.

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

Możliwe rozwiązanie

Stosując tę ​​range operator gem skrypt ten będzie (prawie) powrócić, co chcesz.

Rozpoczyna się od period i odejmuje co jeden po drugim incident.

Od odejmując zakres od drugiego może skutkować w dwóch zakresach, skrypt faktycznie zaczyna [period] i utrzymuje tablicę wolnego incydentu waha się między iteracji:

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] 

Uwagi

zarzuca ona Time#succ jest przestarzały. można dodać

class Time 
    def succ 
    self+1 
    end 
end 

usunięcie ostrzeżenia amortyzacyjne lub użyć Gemfile z:

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

zainstalować nowszą wersję gem, z poprawką na Time.

Skrypt działa z rozdzielczością 1 sekundy, a pierwszy zakres zaczyna się od 09:00:01, ponieważ wystąpił incydent do czasu 09:00:00.