寻找重叠区间，当重叠很少时。

Question

寻找重叠区间，当重叠很少时。

3

我有一个巨大的数据库表，其中包含n个整数区间（例如{1-5}，{4-16}，{6434-114343}），需要找出哪些区间彼此重叠。在stackoverflow上有大量类似的问题，但不同之处在于我需要分别返回每个区间重叠的区间集合。

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

对于这个例子，输出将是A:{B,C,D} B:{A,C} C:{A,B} D:{A} 最坏情况下，所有区间可能彼此重叠，产生大小为O(n²)的输出。这与朴素解决方案（比较每对区间）无异。然而，在实践中，我知道我的区间很少会与其他区间重叠，当它们重叠时，也只有最多5个其他区间。

在这种情况下，我应该如何解决这个问题？（理想情况下，我希望使用SQL查询解决方案，因为数据存储在数据库中，但我认为只有常规算法解决方案才是可能的。）

- Gruber

1

也许你应该在这个上下文中说明“huge”的含义。数千？数百万？数十亿？如果真的存在纯SQL解决方案（我有疑问），您可能希望告诉我们数据如何在数据库中存储，例如您是否有用于范围名称/ ID，间隔开始和结束的单独列，或者开始和结束是否存储为字符串值“x-y”等。还了解数字值的范围可能很有趣，例如可以期望最小/最大间隔开始/结束是什么？ - Mecki

@Mecki：在这种情况下，“huge”表示n=100,000。在数据库中，每个区间都有一个唯一的主键整数值、一个起始整数和一个结束整数。这些数字的范围从0到4*10^9。 - Gruber

2个回答

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

但是如果你已经通过开始时间等方式对间隔进行了排序，则可能在O(n)内完成排序（同样假设交集数量为O(1)）。

- maxim1000

我已经根据您的解决方案，使用数据库存储过程、临时表和游标循环实现了。算法运行非常快，n=100,000时仅需50秒。 - Gruber

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mecki · Accepted Answer

您的问题的典型编程解决方案是构建一个区间树interval tree，然后对每个区间执行一次查找，这将在O(log n)时间内给您所有相交的区间列表。以下是这样一个区间树的示例：

Interval Tree Sample

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

Sample Date Intervals

你的树看起来会像这样。

Sample Tree for Date Intervals

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

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

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

静态关系区间树

他甚至使用了一个巧妙的技巧来优化速度查找，大大减少了CPU使用率，无论是构建查找表还是执行实际查找（这使得整个过程相当复杂）。