arrays - 如何编写一个方法来查找范围数组中的所有交集？

Question

我有类似这样的数组

[
 [0, 10]**,
 [1, 3]**,
 [5, 11]**,
 [14, 20]**,
 [10, 11]**
]

** 表示包含数组中显示的开始和结束索引的对象

现在，交点是 [1, 3]、[5,10]、[10,11]

编写返回包含相交集的对象的方法的最佳方法是什么？ (我们可以将它们存储在一系列相互冲突的东西中)

我遇到的最大问题是如何将每个对象与其他对象进行比较？

有n!这样做的方法(我想，我的组合学有点生疏了)

Answer 1

按开始时间对间隔进行排序(或者按开始时间对索引数组进行排序，这样您就不会丢失索引)。

在此之后，您可以进行一次检测所有交叉点/冲突。

Range array[N];

sort(array);
int i=0;
while(i<N){
    Range curr = array[i];  //invariant: curr doesn't intersect with anyone befor it
    i++;
    while(i < N && array[i].start <= curr.end){
        output that curr and array[i] intersect;
        if(array[i].end > curr.end){
            curr = array[i]
        }
        i++;
    }
}