找到线段的最大长度（扫描线算法）可能是多少

Question

给定一些线段的起始位置，设它们为：1、4、6、9、10。所有线段的长度都相等，记作 C。我们需要找到最大的长度 C，使得不存在一个公共点同时属于 N 条线段。例如，如果 N = 2，给定的线段长度为 4（即 C = 4），那么如果我们按照线段起始位置和终止位置的坐标排序，会得到：[1, 5]，[4, 8]，[6, 10]，[9, 13]，[10, 14]（很容易发现在点 10 处 [6, 10]、[9, 13] 和 [10, 14] 这三条线段相交，违反了条件）。

我知道对于固定端点的线段我有解法，但我不知道如何选择端点，使得公共点不超过 N，而且还要避免 O(n^2) 的迭代。请帮助我。

- Sergey SdZafA

---

在你的例子中，如果 N = 2 和 C = 4，那么 5 不是已经属于两个区间 [1,5], [4,8] 的点了吗？在问题陈述中，你说“没有属于 N 个区间的共同点”，但是这个例子暗示了“没有属于超过 N 个区间的共同点”。 - user1984

转念一想，如果端点是排除在外的，那么你可以认为 5 不属于前一个区间，而 4 不属于下一个区间。因此，为了有效地重叠，两个区间必须共享长度为 2 的完整区间，以便我们得到一个共享点。这就是共同点的定义吗？ - user1984

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之间的任何公共点。

现在，以上意味着为了避免任意两个线段（N = 2）之间有一个共享点，对于0 <= i < len(segment_starts)-1，j = i+1，C必须是min(abs(s_segi - s_segj))+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. 创建一个带有左指针=0和右指针=N-1的滑动窗口或2个指针。您还可以说滑动窗口的长度为N。 2. 跟踪segment_starts[right] - segment_starts[left]的最小值。 3. 在right < len(segment_starts)的情况下运行循环，并在每次迭代后递增left和right。 4. 在循环结束时返回找到的最小值+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

- user1984