hiệu quả Way để Mê của một thời kỳ và Set của dãy trong Ruby

Question

Tôi đã có một số thời gian dao động trong 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'), 
] 

Tôi đang cố gắng để có được một loạt các sự cố khối miễn phí trong vòng thời kỳ. Đối với các trường hợp trên sẽ là:

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

Từ trên có thể xảy ra sự cố chồng chéo hoặc kéo dài ngoài khoảng thời gian. Có bất kỳ hoạt động tồn tại trên phạm vi hoặc một cái gì đó tương tự mà sẽ làm cho loại tính toán đơn giản hơn?

Answer 1

Cho phép full_range là một dải và ranges là một dãy các dải, đại diện cho những gì người hỏi gọi là period và incidents, tương ứng. Tôi đã giả sử các phần tử chứa trong tất cả các phạm vi có thể là bất kỳ đối tượng nào, miễn là chúng có thể được so sánh với phương thức của lớp hiện hành '<=> và mô-đun Comparable đã là include d.

Mã

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 

Ví dụ

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] 

Giải thích

Có lẽ cách dễ nhất và hầu hết thông qua cho tôi để giải thích những gì đang xảy ra là để chèn một số puts báo cáo và chạy mã cho ví dụ đầu tiên ở trên.

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] 

in như sau.

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

giải pháp có thể

Sử dụng range operator gem này, kịch bản này sẽ (hầu như) trả lại những gì mà bạn muốn.

Bắt đầu bằng period và mỗi lần incident cái khác.

Kể từ khi trừ đi một loạt từ khác có thể dẫn đến hai dãy, kịch bản thực sự bắt đầu với [period] và giữ một loạt các sự cố miễn phí nằm trong khoảng giữa lặp:

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] 

Ghi chú

Nó phàn nàn rằng Time#succ là lỗi thời. Bạn có thể có thể thêm

class Time 
    def succ 
    self+1 
    end 
end 

để loại bỏ các cảnh báo không dùng nữa, hoặc sử dụng một Gemfile với:

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

để cài đặt một phiên bản mới hơn của đá quý, với một sửa chữa cho Time.

Tập lệnh hoạt động với độ phân giải 1 giây và phạm vi đầu tiên bắt đầu tại 09:00:01 vì đã xảy ra sự cố cho đến 09:00:00.