1

我们有一个时间框架general_availabilitytime_off（在下图中标记为灰色）与一个时间范围（在下图中标记为黄色）重叠。这种重叠可以采取任何形状，如下图所示。

创建actual_availabilities包括所有时间general_availability但不包括所有时间的第三个时间框架的算法是什么time_off？还有一种可能是actual_availabilities包含多个时间框架general_availability，如下图的第 7 行所示。

我们用 Ruby 编写，但伪代码也会对我们有很大帮助，因为我们主要研究如何解决这个问题的算法。

与下图所示的某些场景相匹配的示例数据和预期输出的一些示例：

从里面开始

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

封闭

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

可能的重叠

更新

这是我最终用 Ruby 编写的代码，它基于 Tamil Velan 的回答。

# 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
4

3 回答 3

1

这个逻辑应该有效

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
        }
    }
}
于 2015-10-15T07:05:34.213 回答
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
 }
}

// 迭代后

打印 aa_array 中的值，它将向我们显示所需的结果

于 2015-10-15T07:10:06.333 回答
1

对于多个超时，只需在循环中运行上述逻辑，如下所示

{
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
}
于 2015-10-15T09:00:12.277 回答