求数组内部间隔的算法

提示:对列表进行排序。

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

对端点进行排序。如果两个端点相等,请在相应的右端点上反向排序。因此[0.1,0.2],[0.1,0.3]将被排序为0.1,0.1,0.2,0.3,其中第一个0.1与第二个间隔。同样,如果右端点相等。

每个端点都应该有对其间隔的引用,这样您就可以找到给定端点的间隔。

扫描已排序的终结点。像你一样,造一棵树。使用[0,1]作为根。节点可以是红色或绿色。一开始是红色的。所以根节点最初是红色的。

树的概念是,最终,如果一个间隔包含另一个间隔,它将成为树中的祖先。如果两个间隔不重叠或部分重叠,它们将位于不同的分支中,并且它们唯一的共同祖先将是根,或包含它们的其他间隔。

当遇到每个左端点时,通过将其间隔的红色节点添加到当前树节点,将其添加到树中的暂定位置。因此,我们遇到的第一个端点会导致相应的间隔被添加到根节点下,并成为当前节点。因此,在遇到其右端点之前,树节点可能有多个附加到它的节点。

当遇到右端点时,其节点将变为绿色,因为我们已经将其从一端完全覆盖到另一端。如果它有任何红色的子节点,则必须移动它们,因为虽然刚刚变绿的节点包含其左端,但它不包含其右端。所以我们将它们全部移到父节点(父节点必须仍然是红色)。

我们继续这个过程,直到到达1.0端点。此时树已完成。所有节点均为绿色。每个节点下的节点表示相应间隔包含的间隔。

1. 根据中断连接的起始点对间隔进行排序,以使较早的端点在稍后出现
2. 注意,按照排序顺序,对于每个元素e,包含e的间隔只能存在于其左侧。
3. 因此,从左开始线性扫描,跟踪到目前为止观察到的最大端点。在任何阶段,如果当前间隔的端点小于最大端点,我们都会找到一个包含在其他端点中的间隔。