3

我有一个带有n 个整数间隔的巨大数据库表（例如 {1-5}、{4-16}、{6434-114343}），需要找出哪些间隔相互重叠。关于 SO有很多 类似的问题，但不同的是我需要分别为每个间隔返回一组重叠间隔。

      ------------------ A -------------------
    ------ B -------               ----- D -----
          --------- C ---------

对于此示例，输出将是A:{B,C,D} B:{A,C} C:{A,B} D:{A}

最坏的情况是，所有区间可能相互重叠，产生大小为 O( n 2 ) 的输出。这并不比简单的解决方案更好（比较每对间隔）。然而，在实践中，我知道我的间隔很少会与其他间隔重叠，而且当它们重叠时，最多只有 5 个其他间隔。

鉴于此信息，我应该如何解决问题？（最理想的情况是，我想要一个 SQL 查询解决方案，因为数据在数据库中，但我认为只有常规的算法解决方案是可能的。）

4

2 回答 2

8

针对您的问题的典型编程解决方案是在所有范围之外构建一个区间树，然后对每个区间执行一次查找，从而O(log n)及时为您提供所有相交区间的列表。这是这样一个区间树的示例：

区间树样本

但是，在您的情况下，您也可以将主键存储在树节点中，因此给定以下日期（查找重叠日期是可以使用区间树解决的常见问题）

样本日期间隔

你的树看起来像这样

日期间隔的样本树

因此，如果我想知道哪些区间与 C 重叠，我会搜索 C 的起点 1843，然后树告诉我，该值仅在区间 C 内，这是我正在测试的区间，所以我可以忽略它。然后我搜索 C 的结尾，1907，树告诉我，它在区间 A、B 和 C 中，我再次可以忽略 C，因此我的结果集是 A 和 B。

我承认，在这样一棵树中的查找并不像人们想象的那么直观。我将尽我所能在这里解释它：您从顶部根节点开始，并在每个节点处决定向左或向右，直到您遇到离开节点（一个不再有子节点的节点）。如果节点值大于您正在搜索的值，则向左走。如果节点值小于您要搜索的值，则向右走。如果您的节点值恰好等于您正在搜索的值怎么办？这取决于！如果您正在搜索区间的开头，则相等的值意味着您向右走，如果您搜索区间的结尾，则相等的值意味着您向左走。这个非常重要。一旦你到达一个离开节点，你就完成了，你在任何节点中找到的所有间隔在前往该离开节点的途中，包括存储在离开节点本身（如果有）中的时间间隔构成了您的结果集，而不仅仅是存储在离开节点中的时间间隔。这意味着您必须收集在执行搜索时遇到的任何间隔。

现在回到你最初的问题：所有这些都可以在 SQL 中完成吗？是的，这是可以做到的。不过，我不确定你是否真的想这样做。您可以将当前的 SQL 表数据转换为表示区间树的 SQL 表，然后直接在该区间树表中执行查找。至少我找到了一个正是这样做的人。他尝试查找涵盖给定日期的所有日期范围，而不必将该日期与数据库中的所有现有范围进行比较：

静态关系区间树

他甚至使用了一个绝妙的技巧来优化查找的速度，显着降低两者的 CPU 使用率，构建查找表并执行实际的查找（这使得整个事情变得相当复杂）。

于 2013-01-08T12:29:56.513 回答
2

建立一个区间开始和结束的排序序列，然后遍历它，每次更新当前区间列表，报告任何新发现的交叉点。

像这样的东西：

std::vector<TBorder> borders;
for(auto i=intervals.begin();i!=intervals.end();++i)
{
    borders.push_back(TBorder(i.Start(),Start));
    borders.push_back(TBorder(i.End(),End));
}
std::sort(borders.begin(),borders.end());
std::set<int> currentIntervals;
for(auto b=borders.begin();b!=borders.end();++b)
{
    if(b.IsEnd())
        currentIntervals.erase(b.IntervalIndex());
    else
    {
        currentIntervals.insert(b.IntervalIndex());
        if(currentIntervals.size()>1)
            ReportIntersection(currentIntervals);
    }
}

通常它是 O(n*log n) （假设交叉点的数量是 O(1) ）。

但是，如果您已经有按例如 start 排序的间隔，则可能的排序可以在 O(n) 中完成（再次假设交叉点的数量是 O(1)）。

于 2013-01-08T12:49:05.917 回答