保留关于两个最大重叠区间max1
和max2
的信息(一开始为空)。
按照x
值对输入列表[x1, y1] .. [xn, yn]
=I1..In
进行排序,如果遇到相等的情况,则丢弃较短的区间。在丢弃区间的同时,保持max1
和max2
更新。
对于每个区间,在线性时间内添加一个属性max
,显示已排序列表中所有前面区间的最大y
值:
rollmax = −∞
for j = 1..n do
Ij.max = rollmax
rollmax = max(rollmax, Ij.y)
在已排序、过滤和扩展的输入列表上执行以下查询。它使用一个不断扩展的区间子列表,作为递归函数
SearchOverlap
的输入,该子列表小于当前搜索的区间
Ii
。
for i = 2..n do
SearchOverlap(Ii, 1, i − 1)
return {max1, max2}
SearchOverlap
函数使用 分治法
遍历排序列表 Il, .. Ir
。它将这样的列表想象成一个完整的二叉树,其中间隔 Ic
是其本地根。测试 Ic.max < I.max
用于始终决定沿着与 I
有最大重叠的间隔方向遍历二叉树(向左/向右)。请注意,I
是查询的间隔,它与 log(n)
其他间隔进行比较。还要注意,在这样的遍历中可能会传递最大可能的重叠间隔,因此需要在函数 SearchOverlap
的开头检查最大重叠。
SearchOverlap(I , l, r)
c = ceil(Avg(l, r)) // Central element of queried list
if Overlap(max1, max2) < Overlap(I , Ic) then
max1 = I
max2 = Ic
if l ≥ r then
return
if Ic.max < I.max then
SearchOverlap(I , c + 1, r)
else
SearchOverlap(I , l, c − 1)
return
最大重叠区间(如果不为空)将在最后返回。总复杂度为O(n log(n))
。