algorithm - 找到段的最大可能长度(扫描线算法)

Question

段(它们的开始)是给定的。设它们为:1、4、6、9、10。所有线段的长度C都相同。我们需要找到这样一个最大长度(C)，使得不存在属于N个线段的公共(public)点。例如，如果 N = 2，并且上面的段的长度为 4 (C = 4)，那么如果我们对段的开始和结束的坐标进行排序，我们得到:[1, 5], [4 , 8], [6, 10], [9, 13], [10, 14](不难注意到在点10 ([6, 10], [9, 13], [10, 14] ) 我们有 3 个线段同时相交，这与条件相矛盾)

我知道段固定端的算法，但我不知道如何选择这样的端，以便在没有 O(n^2) 次迭代的情况下公共(public)点不超过 N。请帮助我

Answer 1

这是一个 O(n)时间复杂度算法，前提是段的开头已经排序。空间复杂度为O(1) .

让我们根据段起点之间的绝对距离来定义共享点的含义。

segment beginnings = [1,_,_,4,_,_,_,8] # empty cells added for illustration
N = 2
if we take C = 5 we get [1,_,_,4,_,_,_,8]
                           1,2,3,4,5
It's evident that there is shared point. If we had C = 4,
this wouldn't be the case since the end points of the segments don't count.

因此，我们可以声明，对于 2 个线段至少有一个共享点，C 的长度必须至少为 abs(s_seg2 - s_seg1) + 2 .这是段开始的距离加 2。这也意味着 C = abs(s_seg2 - s_seg1) + 1避免 seg1 之间的任何共同点和 seg2

现在，上面的意思是为了避免在任何 2 个段 ( N = 2 ) 之间有一个共享点，C必须是 min(abs(s_segi - s_segj))+1对于 0 <= i < len(segment_starts)-1, j = i+1 .

我们如何将这一想法推广到 3 个段 (N = 3) 或任意数量的 2 <= N <= len(segment_starts) 段之间的一个共享点？

对于 3 个相邻的段，s_seg1, s_seg2, s_seg3产生一个共享点3，长度为C必须是 abs(s_seg3 - s_seg1)+2 , 所以 +1将是 C 的最大可能长度.

以上激发了以下算法:

1. 用 left = 0 创建一个滑动窗口或 2 个指针和 right = N-1 .您也可以说 length N 的滑动窗口.
2. 跟踪 segment_starts[right] - segment_starts[left] 的最小值.
3. 运行循环 while right < len(segment_starts)并增加 left和 right每次迭代后。
4. 在循环结束时返回the found min value + 1 .

在伪代码中:

# assuming segment_starts is sorted none-decreasing

if N > len(segment_starts): return Infinity
if N < 2: raise Invalid Input Error

left, right = 0, N-1
curr_best = segment_starts[right] - segment_starts[left]
for right < len(segment_starts):
  curr_best = min(curr_best, segment_starts[right] - segment_starts[left])

return curr_best+1