算法阵列

Question

我有一个包含n个间隔[0,1]

每个间隔看起来像[a(i),b(i)] 0<=a(i)<b(i)<=1 , i = 1...n

我需要找到一种有效的算法中确定每个n个间隔的，如果它的内部包含一个列表内发现间隔其他区间。

我试过很多选择，但我只能找到一个在为O（n^2）

有什么建议？

Answer 1

提示：对列表进行排序。

Answer 2

假设只有一个区间[0,1]。如果它不在列表中，只是为了方便而添加它。

排序端点。在两个端点相同的情况下，在相应的右端点上反向排序它们。因此[0.1,0.2]，[0.1,0.3]将被排序为0.1,0.1,0.2,0.3，其中第一个0.1以第二间隔进行。同样如果右端点是相等的。

每个端点都应该有一个对其间隔的引用，以便您可以找到给定端点的时间间隔。

扫描排序的端点。和你一样，建立一棵树。使用[0,1]作为根。节点可能是红色或绿色。他们从红色开始。所以根节点最初是红色的。

树的想法是，如果一个区间包含另一个区间，那么它最终将成为树中的祖先。如果两个区间不重叠或部分重叠，它们将位于不同的分支中，并且它们唯一的共同祖先将是根，或者包含它们的其他区间。

当遇到每个左端点时，通过向其当前树节点添加一个红色节点作为其间隔，将其添加到树中的临时位置。因此，我们遇到的第一个端点会导致相应的时间间隔被添加到根目录下，并成为当前节点。因此，在遇到右手端点之前，树节点可能会连接多个节点。

当遇到右手端点时，其节点变为绿色，因为我们已经从一端到另一端完全覆盖了它。如果它有任何红色的后代，它们必须被移动，因为当正好转向的绿色节点包含它们的左端时，它不包含它们的右端。所以我们把它们全部移到父节点（它仍然是红色的）。

我们继续这个过程，直到我们到达1.0端点。此时树完成。所有节点都是绿色的。每个节点下的节点表示对应的时间间隔包含的时间间隔。

Answer 3

1. 排序根据自己的起点打破关系，使得早期的端点出现后
2. 观察到，在排定的顺序，每一个元素E的间隔，含值e只能存在于它的左边。
3. 因此从左侧线性扫描到目前观察到的最大终点的轨迹。在任何阶段，如果当前时间间隔的终点小于最大终点，我们发现一个包含在另一个时间间隔内的时间间隔。