Java算法：查找区间交集

Question

我有一个时间间隔，如下所示：

[5,10]

我有更多的时间点列表，长度不同，例如：

t1=[3,6,9,10] 
t2=[2,4,5,6,10]
..

t1 [3,6] 是第一个区间，[6,9] 是第二个区间，以此类推。

t2 和其他列表也是同样的情况。

现在我需要保存与第一个时间间隔相交的列表和特定时间间隔。例如，在t1中，我有[3,6]与[5,10], [6,9]相交，等等。

我已经制定了一个算法，但我需要处理更多的数据并且需要快速算法。例如，如果我处理300.000个列表，每个列表有200个时间点，那么我的算法在5-10秒内可以正常运行。但是如果时间点有10.000个或更多，则算法非常慢。

我的算法如下：

First time interval <- [t1,t2]
For each list
  For each time interval [s1,s2] in list
     if(s1>= t1 && s2 <= t2)
     {
         saveIntervall()
     }
     else if (s1<= t2 && s2 > t2)
     {
         saveIntervall()
     }
     else if(s1 <  t1 && s2 >= t1)
     {
        saveIntervall()
     }
     else if (s1 < t1 && s2 > t2)
     {
        saveIntervall()
     }

编辑1：是的，我有一个有序列表。

编辑2：我还有另一个问题，当我找到交集时，我需要计算一个介于0和1之间的得分，表示交集的大小。 我使用以下代码：

            double score = 0.0d;
        if(s1>= t1 && s2 <= t2)
        {
            score = (s2-s1) / (t2-t1);
        }
        else if(t2 >= s2 && t1 > s1)
        {
            score = (s2-t1) / (t2-t1);
        }
        else if(t2 < s2 && t1 <= s1)
        {
            score = (t2-s1) / (t2-t1);
        }
        else
        {
            score = 1;
        }

我也可以加快速度吗？

- Neptune

---

你的列表有序吗？此外，我认为这里已经有一个答案了：https://dev59.com/S3VC5IYBdhLWcg3wZwXj - Jorge Campos

这些数组中有超过两个数字是什么意思？t1看起来只是一对区间，但我不明白t2如何映射到区间。 - dimo414

如果我理解得正确，区间由一个元素和下一个元素组成。所以列表至少需要有两个值。 - Jorge Campos

在“第一时间间隔”中，我犯了一个错误，只有一个时间间隔。在另一个列表中，时间间隔由一个元素和下一个元素组成，就像Jorge所说的那样。 - Neptune

你的搜索列表是否总是只有两个元素？ - Chris K

Answer 1

如果两个区间 [s1, s2] 和 [t1, t2] 的交集为空，则 当且仅当:

    t2 < s1 or s2 < t1

所以，要检查两个时间段是否相交，您只需要执行上述测试。

而且，一旦您知道s2 < t1，那么就没有必要继续在带有t1的列表上进行，因为更大的时间段永远不会相交，这意味着您应该继续移动。

简单伪代码：

   given [s1, s2]
   for each list [t1, t2, ... t(n)] in search_lists
        for each interval [t(x), t(x+1)] from [t1, t2, ... t(n] (x goes from 0 to n-1)
           if t(x+1) < s1
              continue
           if s2 < t(x)
              break
           saveInterval()

这个内容可以进行改进以更好地利用[t1，t2，...，t(n)]已排序的事实。

首先注意到[s1，s2]将与[t(x)，t(x+1)]相交当且仅当t(x+1) >= s1且s2 >= t(x)

然而

if t(x) >= s1 then for every h>0      `t(x+h) >= s1` 

also

if s2 >= t(x) then for every h>0  `s2 >= t(x-h)`

因此，如果我们找到最小的i，使得t(i + 1) > = s1，则从[t（i），t（i + 1）]开始的所有区间都符合交集的第一个条件; 即 ([t（i + 1），t（i + 2）]，[t（i + 2），t（i + 3）] ...)

如果我们找到最大的j，使得s2>= t(j-1)，则从[t（j-1），t（j）]向后的所有区间都符合交集的第二个条件。即 ([t（j-2），t（j-1）]，[t（j-3），t（j-2）]...)

在i和j之间的所有区间同时满足这两个条件。

所以最终的算法是：

given [s1, s2]
for each list [t1, t2, ... t(n)] in search_lists
    find the smallest i such that t(i+1)>=s1  
    find the biggest  j such that s2>= t(j-1)

    if j>i then all the intervals between `{t(i)... t(j)}` intersect with [s1, s2]
    otherwise there is no intersection.       

由于{t1, t2, t3...t(n)}已经排序，我们可以使用二分搜索有效地找到索引i和j

编辑2:

[s1,s2]和[t1,t2]的交集为：
[max(s1,t1),min(s2,t2)]

它们的大小是： L1 = s2-s1 L2 = t2-t1 L3 = min(s2,t2) - max(s1,t1)

你要找的分数是：L3/min(L2,L1)，一个介于0和1之间的分数。

(min(s2,t2) - max(s1,t1)) / ( min(s2-s1, t2-t1) )

计算这个的成本是3个测试、3个减法运算和一个浮点数运算。 但我假设间隔是有效的，而且交集存在，否则需要更多的测试。(s2>s2, t2>t1 和 min(s2,t2) > max(s1,t1)。最后一个测试与上面讨论中的相交条件相同。)

- odedsh

---

在有序列表中，他也可以省略t2<s1的检查。用语言表达就是：“如果下一个区间开始时间早于当前区间结束时间：匹配”。 - dognose

Answer 2

首先，你的数据结构很混乱 - 如果你想要讨论离散的时间间隔，请按以下方式构建你的数据结构;例如int[][]，其中内部数组始终为长度2，因此你的t1变成：

int[][] t1 = {{3,6}, {6,9}, {9,10}};

使用正确的结构可能会帮助您简化算法并使其更易于处理。

---

比正确结构化的数组更好的是，使用专门的类型来表示这些间隔，这样你就可以传递 List<Interval> 对象并对它们进行某种包含检查。但不要重复发明轮子。强大的Guava库提供了一个健壮的Range类，您可以使用它。更好的是，它还提供RangeSet和RangeMap类，让您轻松地完成您所说的事情。另请参阅他们的范围解释文章，介绍了基础知识。

请注意，如果您无法从外部重新设计数组结构，则可以相当轻松地将当前设计转换为内部的Range对象。

曾经尝试构建自己的IntervalSet类，让我告诉你，这是一个棘手的问题，你会节省很多时间使用他们经过精心设计和高度测试的范围工具。

以下是我使用Guava描述您所描述的方式的方法-请注意，我们甚至避免需要考虑涉及的数学问题-Range已经为我们做好了正确的事情：

/**
 * Given a Range and an group of other Ranges, identify the set of ranges in
 * the group which overlap with the first range.  Note this returns a Set<Range>
 * not a RangeSet, because we don't want to collapse connected ranges together. 
 */
public static <T extends Comparable<?>> Set<Range<T>>
        getIntersectingRanges(Range<T> intersects, Iterable<Range<T>> ranges) {
    ImmutableSet.Builder<Range<T>> builder = ImmutableSet.builder();
    for(Range<T> r : ranges) {
        if(r.isConnected(intersects) && !r.intersection(intersects).isEmpty()) {
            builder.add(r);
        }
    }
    return builder.build();
}

/**
 * Given a 2-length array representing a closed integer range, and an array of
 * discrete instances (each pair of which therefore represents a closed range)
 * return the set of ranges overlapping the first range.
 * Example: the instances array [1,2,3,4] maps to the ranges [1,2],[2,3],[3,4].
 */
public static Set<Range<Integer>> getIntersectingContinuousRanges(int[] intersects,
        int[] instances) {
    Preconditions.checkArgument(intersects.length == 2);
    Preconditions.checkArgument(instances.length >= 2);
    ImmutableList.Builder<Range<Integer>> builder = ImmutableList.builder();
    for(int i = 0; i < instances.length-1; i++) {
        builder.add(Range.closed(instances[i], instances[i+1]));
    }
    return getIntersectingRanges(Range.closed(intersects[0], intersects[1]),
                                 builder.build());
}

使用您的示例：

public static void main(String[] args)
{
    int[] interval = {5,10};
    int[] t1 = {3,6,9,10};
    int[] t2 = {2,4,5,6,10};

    System.out.println(getIntersectingContinuousRanges(interval, t1));
    System.out.println(getIntersectingContinuousRanges(interval, t2));
}

上面的代码将输出：

[[3‥6], [6‥9], [9‥10]]
[[4‥5], [5‥6], [6‥10]]

- dimo414

Answer 3

给定两个区间的左边界和长度，可以使用以下代码测试它们是否相交。

protected boolean intervalOverlap( int pos1, int length1, int pos2, int length2 ){
  int pos_A_left  = pos1;
  int pos_A_right = pos1 + length1;
  int pos_B_left  = pos2;
  int pos_B_right = pos2 + length2;
  return pos_B_left < pos_A_right && pos_A_left < pos_B_right;
}

有一篇短小的文章讨论了这种方法。此外，还介绍了区间的另一种表示方法（使用中心和长度），可以更高效地实现交集测试。

- Codor