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
| ruby   | algorithm   2016-12-22 19:12 2 Answers

Answers ( 2 )

  1. 2016-12-22 23:12

    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. 2016-12-23 07:12

    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 included.

    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] 
    
◀ Go back