Search code examples
rubyalgorithmlanguage-agnosticinterval-intersection

Algorithm to reduce one time frame by another time frame

We have a time frame general_availability (marked as grey in the image below) that overlaps with a time frame time_off (marked as yellow in the image below). This overlap can take any shape as shown in the image below.

What's the algorithm to create a third time frame actual_availabilities that includes all time of general_availability but excludes all time of time_off. There's also a possibility that actual_availabilities consists of multiple time frames if 'time_off' is enclosing general_availability as shown for example in the 7th row of the image below.

We write in Ruby but pseudo code will help us a lot, too, as we're mainly after the algorithm on how to approach this problem.

Some examples of sample data and expected output that match some of the scenarios shown in the image below:

Start inside

general_availability = #<Availability start_time: "2016-04-13 15:00:00", end_time: "2016-04-13 18:00:00">
time_off = #<Availability start_time: "2016-04-13 13:00:00", end_time: "2016-04-13 16:00:00">
actual_availabilities = [#<Availability start_time: "2016-04-13 16:00:00", end_time: "2016-04-13 18:00:00">]

Enclosing

general_availability = #<Availability start_time: "2016-04-13 15:00:00", end_time: "2016-04-13 22:00:00">
time_off = #<Availability start_time: "2016-04-13 17:00:00", end_time: "2016-04-13 18:00:00">
actual_availabilities = [#<Availability start_time: "2016-04-13 15:00:00", end_time: "2016-04-13 17:00:00">, #<Availability start_time: "2016-04-13 18:00:00", end_time: "2016-04-13 22:00:00">]

Possible overlaps

Update

Here's the code I ended up in Ruby, it's based on Tamil Velan's answer.

# Algorithm based on http://stackoverflow.com/a/33142065/1076279
def merge_time_ranges(available_time_range, unavailable_time_ranges)
  merged_time_ranges = []

  if unavailable_time_ranges.empty?
    merged_time_ranges << {start_time: available_time_range[:start_time], end_time: available_time_range[:end_time]}
  else
    revised_available_start_time = available_time_range[:start_time]
    revised_available_end_time = available_time_range[:end_time]

    unavailable_time_ranges.each_with_index do |unavailable_time_range, index|
      # Skip if one unavailable time range covers all of the available time range (person doesn't work that day)
      #   |---- Available time -----|
      # |------ Unavailable time -------|
      if (available_time_range[:start_time] >= unavailable_time_range[:start_time]) && (available_time_range[:end_time] <= unavailable_time_range[:end_time])
        break

      # Don't change anything unless the two blocks (available and unavailable time) overlap
      # http://stackoverflow.com/a/325964/1076279
      # |---- Available time -----|
      #                                 |--- Unavailable time ----|
      #
      #                     OR
      #
      # http://stackoverflow.com/a/325964/1076279
      # |---- Unavailable time -----|
      #                                 |--- Available time ----|
      elsif !((revised_available_start_time <=  unavailable_time_range[:end_time]) && (revised_available_end_time >= unavailable_time_range[:start_time]))
        # Do nothing

      # Reduce end time of available time
      # |---- Available time -----|
      #                   |--- Unavailable time ----|
      #
      #                     OR
      #
      # |------------- Available time --------------|
      #                   |--- Unavailable time ----|
      elsif (unavailable_time_range[:start_time] > revised_available_start_time) && (unavailable_time_range[:end_time] >= revised_available_end_time)
        revised_available_end_time = unavailable_time_range[:start_time]

      # Reduce start time of available time
      #             |---- Available time -----|
      # |--- Unavailable time ----|
      #
      #                     OR
      #
      # |--------------- Aavailable time ----------------|
      # |- Unavailable time -|
      elsif (revised_available_start_time >= unavailable_time_range[:start_time]) && (revised_available_end_time > unavailable_time_range[:end_time])
        revised_available_start_time = unavailable_time_range[:end_time]

      # Create block and reduce available start time
      # |--------------- Aavailable time ----------------|
      #         |- Unavailable time -|
      elsif (revised_available_start_time < unavailable_time_range[:start_time]) && (revised_available_end_time > unavailable_time_range[:end_time])
        if unavailable_time_range[:start_time] >= (revised_available_start_time + 1.hour) # don't create availabilities of less than an hour
          merged_time_ranges << {start_time: revised_available_start_time, end_time: unavailable_time_range[:start_time]}
        end
        revised_available_start_time = unavailable_time_range[:end_time]
      end

      # Add last block
      if (index == unavailable_time_ranges.size - 1) && (revised_available_end_time >= revised_available_start_time + 1.hour) # don't create availabilities of less than an hour
        merged_time_ranges << {start_time: revised_available_start_time, end_time: revised_available_end_time}
      end
    end
  end

  merged_time_ranges
end
Solution 
  • // Fetch a record for a given day
// variables to hold the values of general_availability
var ga_start_time, ga_end_time

var aa_array - array to store the actual availability on a given day

var rev_ga_start_time = ga_start_time - Initial value of rev_ga_start_time(revised general availability start time) should be the same as general availability start time

Iterate the time_off array and for each iteration perform the below 

var to_start_time, to_end_time; - to be filled from the iteration of time_off array

// start time of time_off and end time of time_off falls within general_availability time

if ( ga_start_time >= to_start_time and ga_end_time <= to_end_time) {
// Break the iteration and exit.
// This person is not working for the given day
}

if (rev_ga_start_time >= to_start_time) {
 rev_ga_start_time = to_end_time
} else if (rev_ga_start_time < to_start_time) {
 [rev_ga_start_time, to_start_time] add this to aa_array
 rev_ga_start_time = to_end_time
} 

if( last iteration) {
  if( rev_ga_start_time != ga_end_time or if rev_ga_start_time < ga_end_time) {
   [rev_ga_start_time, ga_end_time] add this to aa_array
 }
}

    // After iteration

    Print the values in aa_array, it will show us the desired result