一种有效的方法来找出Ruby中一个时段和一组范围的差异

Question

我在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'),
]

我正试图在这段时间内获得一系列事件免费块.对于上面那个是:

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

从上面可以看出事件在这段时间之外重叠或延伸.范围或类似的任何操作是否会使这种计算更简单？

Answer 1

设full_range是一个范围 和ranges是一个范围数组，分别代表提问者所说的period和incidents。我假设所有范围中包含的元素可以是任何对象，只要它们可以与适用的类的方法进行比较<=>并且模块Comparable已经被include创建。

代码

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

例子

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]  

解释

也许对我来说解释正在发生的事情的最简单、最彻底的方法是插入一些puts语句并运行上面第一个示例的代码。

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]

打印以下内容。

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]