求区间交集的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] 相交，与 [5,10]等

我已经制定了一个算法，但我要处理更多数据，我需要一个快速算法。例如，如果我使用 300.000 个列表并且每个列表都有 200 个时间点，我的算法 1 在大约 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()
     }

Edit1:是的，我已经订购了 list 。

Edit2:我还有另一个问题，当我找到交点时，我需要计算一个介于 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;
        }

我也可以加快速度吗？

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)] iff t(x+1) >= s1 和 s2 >= t(x)

但是

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

还有

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]的交集是:
[最大(s1, t1), min(s2,t2)]

大小是:L1 = s2-s1L2 = t2-t1L3 = 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 次减法运算和 1 次浮点运算。但我假设间隔有效并且存在交集，否则需要更多测试。 (s2>s2, t2>t1 and min(s2,t2) > max(s1,t1)。最后的测试是一样的iff 上述讨论的交集条件。