1

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
migu
  • 4,236
  • 5
  • 39
  • 60
  • 1
    Your question is not clear. You have not defined "General Availabillity" or "Time Off", and have not related those terms to the table. I'm guessing "Time Off" is the time interval shown in grey. If so, does part of the "Start Inside" task have to be past the grey area or does the start time of that task have to be after the grey area? Lastly, you need to provide example input comprised of Ruby objects and the corresponding desired output. Be sure to assign each input object to a variable (e.g., `tasks = { "start"=>(0..7),...}; time_out = (10..18)` if periods are given by integers. (cont...) – Cary Swoveland Oct 15 '15 at 02:23
  • 1
    (...cont.) In doing that, you could simplify the problem to having only a subset of the tasks shown in your table. If you take my advice, it will take some time to edit your question. I therefore suggest you delete it, make the edits, then undelete. – Cary Swoveland Oct 15 '15 at 02:25
  • Thanks for your feedback. I have modified the question, I hope it makes things more clear. Let me know if it needs further editing. – migu Oct 15 '15 at 03:23
  • 1
    Will there be multiple time_offs allowed in your system? ex. time_off on 15Oct2015 13:00:00 to 14:00:00 and 15:00:00 to 16:00:00 – Clement Amarnath Oct 15 '15 at 05:32
  • @ClementAmarnath Yes. – migu Oct 15 '15 at 05:47

3 Answers3

1

This logic should work

if((timeoff_start >= generaltime_end) || (timeoff_end <= generaltime_start))
{
    // After, Start Touching, End Touching and Before case
    Actual availability = generaltime
}
else if((timeoff_start <= generaltime_start) && (timeoff_end >= generaltime_end))
{
    // Inside start touching, Inside, Inside End touching and Exact case
    Actual availability = 0
}
else
{
    /* All remaining cases */

    if(timeoff_start <= generaltime_start)
    {
        // Start inside & Enclosing Start Touching case
        Actual Availablity = timeoff_end to generaltime_end
    }
    else 
    {
        if(timeoff_end < generaltime_end)
        {
            // Enclosing case
            Actual Availability1 = generaltime_start to timeoff_start
            Actual Availability2 = timeoff_end to generaltime_end
        }
        else
        {
            // End Inside and enclosing end touching case
            Actual Availability = generattime_start to timeoff_start
        }
    }
}
Tamil Velan
  • 15
  • 4
1
// 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

Clement Amarnath
  • 5,301
  • 1
  • 21
  • 34
  • 1
    Very good, thanks. For the "End Inside" case shown in the picture, I think the last block needs an additional condition (`if rev_ga_start_time != ga_end_time` or `if rev_ga_start_time < ga_end_time`), otherwise an array member with `rev_ga_start_time == ga_end_time` is being created. Example values would be general availability from 3 to 9pm and time off from 6pm to 10pm. The current code would add an array member [10pm, 10pm], correct? – migu Oct 16 '15 at 22:37
  • Yes you are correct. I have added this condition in the answer. – Clement Amarnath Oct 19 '15 at 05:14
1

For multiple timeoff just run the above logic in loop as below

{
timeoff[] /* Array of timeoffs 
           * i2to -Index to Timeoff */
generaltime[] /* Array of generaltime, initially it contains only one entry
               * at the end of execution generaltime contains all the availability times
               * i2gt - Index to Generaltime */
do /* For each entry in timeoff
{
    do /* for each entry in generaltime
    {
        if((timeoff[i2to].start <= generaltime[i2gt].start) && (timeoff[i2to].end >= generaltime[i2gt].end))
        {
            /* Current timoff is in Inside start touching, Inside, Inside End touching and Exact case. 
             * So, this can not be part of available time. clear current generaltime 
            generaltime[i2gt].start = generaltime[i2gt].end = 0;
        }
        else if((timeoff[i2to].start >= generaltime[i2gt].end) || (timeoff[i2to] <= generaltime[i2gt].start))
        {
            /* Current timeoff is in After, Start Touching, End Touching and Before case
             * Leave the generaltime as it and it will make to acutalTime
        }
        else
        {
            /* All remaining cases */

            if(timeoff_start <= generaltime_start)
            {
                /* Start inside & Enclosing Start Touching case
                 * Cut overlapped timeoff from general_time
                generaltime[i2gt].start = timeoff[i2to].end 
            }
            else 
            {
                if(timeoff_end < generaltime_end)
                {
                    /* Enclosing case
                     * Split the general time in to two

                    /* First entry has generaltime[i2gt].start to timeoff[i2to].start
                    generaltime[i2gt].end = timeoff[i2to].start 

                    /* Create new entry in the generaltime by pushing out remaining entries to */
                    Push entries from i2gt+1 to numgt to i2gt+2 to numgt+1
                    generaltime[i2gt+1].start = timeoff[i2to].end 
                    generaltime[i2gt+1].end = generaltime[i2gt].end
                    numgt++;
                }
                else
                {
                    /* End Inside and enclosing end touching case
                     * Cut overlapped timeoff from general_time
                     generaltime[i2gt].end = timeoff[i2to].start
                }
            }
        }
    } while(more entries in generaltime)
} while (more entries in timeoff)

/* Generaltime contains all actual availability time
Display all entries in generaltime
}
Tamil Velan
  • 15
  • 4