## Efficient Way to Find the Difference of a Period and Set of Ranges in Ruby

Question

I've got a number of time ranges 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'),
]
``````

I'm trying to get an array of incident free blocks within the period. For the above that'd be:

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

From the above it is possible for incidents to overlap or extend outside the period. Do any operations exist on range or something similar that would make this sort of calculation simpler?

Show source

1. # Possible solution

Using this range operator gem, this script would (almost) return what you want.

It begins with `period`, and substracts every `incident` one after the other.

Since substracting a range from another can result in two ranges, the script actually begins with `[period]` and keeps an array of free incident ranges between iterations :

``````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]
``````

# Notes

It complains that `Time#succ` is obsolete. You can either add

``````class Time
def succ
self+1
end
end
``````

to remove the deprecation warnings, or use a Gemfile with :

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

to install a newer version of the gem, with a fix for `Time`.

The script works with a resolution of 1 second, and the first range begins at `09:00:01` because there was an incident until `09:00:00`.

2. Let `full_range` be a range and `ranges` be an array of ranges, representing what the asker termed `period` and `incidents`, respectively. I've assumed the elements contained in all ranges can be any objects, provided they can be compared with the applicable class' method `<=>` and that the module Comparable has been `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
``````

Examples

``````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]
``````

Explanation

Perhaps the easiest and most through way for me to explain what's going on is to insert some `puts` statements and run the code for the first example above.

``````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]
``````

prints the following.

``````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]
``````