3

给定一个包含 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]

这里我们有包含 ecb 的 f 和最大的 d。当然，g 要长得多，但不包含任何其他段，所以这不是最大段的问题。

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

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

对我来说主要的问题是我不能排除一段时间处理段，因为在某些时候可能会出现不包含在 f 中的子段并构成最大的段。

4

2 回答 2

2

我在 O(n log n) 中找到了直接解决方案。

使用字典顺序对段进行排序，首先按 x 坐标的升序，然后按 y 坐标的降序。鉴于此顺序，如果段 (a,b) > (a',b')，我们保证 a > a' 或 a=a' 但 b < b'。无论哪种方式，(a,b) 都不能包含 (a',b')。剩余段的数量是 n 减去该排序数组中段 k 的索引。让我们记下这些段。

在这些段中，我们可以使用相反的顺序（减少 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。

于 2013-03-06T17:34:26.217 回答
2

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)。

于 2013-03-06T17:17:33.300 回答