计算最大子段数的算法

Question

给定一个由n个整数段组成的向量，我正在寻找一种O(n log n)算法来计算包含最多其他段的段。实际上，我只对这些段的数量感兴趣。

我尝试了各种变化的区间树和线段树，但都不相关。真正的问题在于部分顺序。如果顺序是总的，那么通过直接计算包含树来解决问题就容易得多。

例如：a = [4;11] b = [2;7] c = [5;8] d = [6;7] e = [3;9] f = [1;10] g = [10;42] 在这里，我们有f包含e、c、b和d，而d是最大的。当然，g要长得多，但不包含任何其他段，所以这不是最大段的问题。

我们可以显示顺序图（不显示传递弧）：

f -----> b  ---> d
  \-->e--->c-/
       a-/
g

对我来说主要问题在于，在处理段时无法排除某些子段，因为有时会出现未包含在f中的子段，从而使a成为最大的段。

- deufeufeu

---

你的子段可以有子段吗？也就是说，它可以有多个层次吗？ - christopher

如果你附近有大学图书馆，可以在这里尝试：http://www.amazon.co.uk/Foundations-Multidimensional-Structures-Kaufmann-Computer/dp/0123694469 - Meirion Hughes

你如何定义包含？为什么[4;11]被认为包含在[1;10]中，但[10;42]却不包含在[4;11]中？ - Vaughn Cato

你确定图的深度和“最大”段中包含的段数是等价的吗？[1,20]包含四个段：[1,2]，[3,4]，[5,6]，[7,8]，但图的深度仅为1。在这种情况下，你想要哪个数字？ - Rafał Dowgird

你说得对。我正在寻找的实数是顶点图中最大星形子图的基数。我不知道这个有没有名字。 - deufeufeu

Answer 1

如果假设没有端点重叠，那么O(n log n)是可行的（我假设使用开放区间）

将所有端点按顺序排序（升序），并跟踪每个点属于哪个区间（例如使用ID）以及该点属于区间的哪一端。

现在您需要维护一个支持以下操作的数据结构：

AppendAtEnd(interval_id)
int GetPosition(interval_id)
Value Remove(interval_id)
IncrementValuesLessThanPosition(j)

这是一个结构体，它接受一个关键字（intervals_ids）并维护一个已排序的列表（按插入时间排序），其中包含一个附加值，最初为0，我们用它来跟踪子间隔。

它允许您在末尾插入。使用ID删除（并获取相应的值），获取 ID 的位置（可以将其视为从头部开始的距离，如果使用链接列表实现），并递增列表特定前缀的所有值。

为了将此结构用于我们的问题，我们遍历上述排序列表，并每次看到一个间隔的左端点时，我们调用 AppendAtEnd。

每次看到间隔的右端点时，我们获取其位置，将其删除，并递增小于该位置的所有值（基本上所有具有此已删除间隔作为子间隔的间隔）。

使用平衡树和适当的修饰信息（如子树总和和节点计数），这是可行的，以使每个操作的时间复杂度为 O(log n)。

- WhoCares

---

谢谢你的回答。但是我已经找到了一种使用普通数组的解决方案。 - deufeufeu

Answer 2

我已经找到了一个O(n log n)的直接解决方案。

首先按字典顺序对线段进行排序，先按x坐标递增排序，然后按y坐标递减排序。在这个顺序下，如果有一条线段（a，b）> （a'，b'），我们可以确保要么a> a'，要么a = a'但b < b'。无论哪种方式，（a，b）都不能包含（a'，b'）。剩余线段的数量是n减去线段k在这个排序数组中的索引。让我们用Sk表示这些线段。

对于这些线段，我们可以使用相反的顺序（y坐标递减，然后x坐标递增），并且线段k的索引等于Sk中未包含在线段k中的线段数。

这里的技巧在于直接计算包含的线段很难，但是计算左侧（或右侧）包含的线段+非包含线段很容易。

总之，伪代码如下：

segments as triples (low,high,id)
orderedXY = sort segments first inc. x then dec. y then inc. id
orderedYX = sort segments first dec. y then inc. x then inc. id
return max(n - orderedXY.find(id=k) - orderedYX.find(id=k) - 1, for every id k)

由于两次排序，该算法的时间复杂度为O(n log n)。

编辑：为了处理重复的片段，我们需要按照第三个键（即片段的id）进行排序。这样可以保证排序是稳定的。

编辑'：为确保每个片段仅计数一次，我们需要减去1。

- deufeufeu

---

优秀的解决方案。我已经找到了这个关系，但仍在思考它为什么有效。从排除的片段推理确实更容易。我认为您将每个片段都计算为包括自身，并且需要减去1。负数意味着一个区间被重复计算，因此它是某个东西包含在其中的区间数量。 - micans

是的，确实如此。我需要减去1。谢谢。 - deufeufeu