将一个时间框架减少另一个时间框架的算法
Algorithm to reduce one time frame by another time frame
我们有一个时间范围 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
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
#
# |---- Available time -----|
# |--- Unavailable time ----|
#
# OR
#
#
# |---- 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
这个逻辑应该可行
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
}
}
}
// 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中的值，它会显示我们想要的结果
对于多次休假只需运行上面的逻辑循环如下
{
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
}
我们有一个时间范围 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
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
#
# |---- Available time -----|
# |--- Unavailable time ----|
#
# OR
#
#
# |---- 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
这个逻辑应该可行
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
}
}
}
// 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中的值，它会显示我们想要的结果
对于多次休假只需运行上面的逻辑循环如下
{
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
}