ruby - 将一个时间框架减少另一个时间框架的算法

Question

我们有一个时间范围 general_availability(在下图中标记为灰色)与时间范围 time_off(在下图中标记为黄色)重叠。这种重叠可以是任何形状，如下图所示。

创建第三个时间范围 actual_availabilities 的算法是什么，它包括 general_availability 的所有时间但不包括 time_off 的所有时间。如果“time_off”包含 general_availability，则 actual_availabilities 也有可能包含多个时间范围，如下图第 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

Answer 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中的值，它会显示我们想要的结果