migu migu - 6 months ago 21
Ruby Question

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

Answer
// 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

Comments