我有两个数组,一个是已存在约会的数组,另一个是潜在约会的数组。每个数组都包含现有或潜在约会的起始和结束时间值。每个数组中的约会已按照起始时间排序。
我需要检查每个潜在约会是否与每个现有约会有重叠。虽然我可以每次从现有约会的开头开始检查,但我正在寻找更高效的方法。
我需要检查每个潜在约会是否与每个现有约会有重叠。虽然我可以每次从现有约会的开头开始检查,但我正在寻找更高效的方法。
A
仅按endtime排序,开始时间可以是任何顺序。假设A
中的所有间隔都在s
之后结束,但只有最后一个间隔在t
之前开始。然后,您需要检查A
的所有元素以查找重叠的间隔。 - BKEOverlaps(actual[1..n], pending[1..m])
i = 1
j = 1
while i <= n and j <= m do
if actual[i].stop <= pending[j].start then
i = i + 1
else if actual[i].start >= pending[j].stop then
j = j + 1
else
return true
return false
actual[i].stop <= pending[j].stop
,则增加i,或者如果actual[i].stop > pending[j].stop
,则增加j。这将打印出每个重叠的对,并仍然保持线性时间。您可以将现有和潜在的约会合并到一个数组中,并按开始时间对联合进行排序。为时间间隔添加标签,以确定是现有还是潜在的时间间隔。(您也可以将它们分别排序到不同的数组中,并递增两个索引,但使用一个列表的代码更简单)。
然后,您可以循环遍历组合数组,并在它们重叠时合并相邻的时间间隔。只合并现有的约会和现有的约会,同样地,只合并潜在的约会和潜在的约会。为此,您需要记住最近的现有和潜在的时间间隔。
通过这种方式,您不需要回到最开始的地方,只需要查看最近合并的时间间隔。
伪代码如下:
E: existing appointments
P: potential appointments
A: union of P and E, sorted by start time
lastE = []
lastP = []
for each appointment a in A:
if a is existing:
if a overlaps with lastE:
lastE = lastE + [a]
else
lastE = [a]
if a overlaps with lastP:
print all appointments in lastP overlapping with a
if a is potential:
if a overlaps with lastE:
print a
if a overlaps with lastP:
lastP = lastP + [a]
else:
lastP = [a]
lastE
的结构,可以将其定义为单个时间段并调整开始和结束时间。lastP
中的各个预约。通过在lastP
中按结束时间维护降序,您可能甚至可以进一步优化它。然后,在打印出a
和lastP
之间的所有重叠时,您可以一旦看到lastP
中潜在预约的结束时间小于a
的开始时间,就可以停止查找。