如何编写一种在范围数组中找到所有交点的方法？ [英] How do I write a method that finds all the intersections in an array of ranges?

问题描述

我有与此类似的数组

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

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

** Denotes an object containing the start and end indexes shown in the array

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

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

What is the best way to write a method that returns the objects containing of the intersecting sets? (Could just store them in an array of conflicted stuff as we go along)

我遇到的最大问题是如何做到这一点每个对象都与其他对象进行比较？

The biggest issue I'm having is how do I do this such that each object is compared with eachother object?

有n个！做到这一点的方法（我认为我的组合学有点生锈）

there are n! ways to do this (i think, I'm a bit rusty on my combinatorics)

推荐答案

按开始时间对时间间隔进行排序（或改为按开始时间对索引数组进行排序，这样就不会丢失索引。）

Sort the intervals by start time (or instead sort an array of indices by start time so you don't lose the indices).

在此之后，您可以执行一次遍历检测所有交叉点/冲突。 / p>

After this you can do a single pass detecting all intersections/conflicts.

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++;
    }
}

这篇关于如何编写一种在范围数组中找到所有交点的方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！