How do I write a method that finds all the intersections in an array of ranges?

Question

I have array similar to this

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

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

Now, the intersections are [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?

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

start and end indices of text blocks from large-ish pieces of text. — NullVoxPopuli, Oct 31 '11 at 20:57
Could you explain how you get from the starting data to the intersections and the conflicting sets? That's not clear at all. — Matt Fenwick, Oct 31 '11 at 21:02
What have you tried? I take it you want the intersecting pairs to be `(0, 1), (0, 2), (0, 4), (2, 4)`. — Jim Mischel, Oct 31 '11 at 21:06
@MattFenwick, how I get the data isn't important, I don't think. — NullVoxPopuli, Oct 31 '11 at 21:12
@JimMischel I'm stuck on the comparing each object to every other object part. I'm thinking I might need to do something recursive. =\ — NullVoxPopuli, Oct 31 '11 at 21:13
You might look into interval trees: http://www.dgp.toronto.edu/~jstewart/378notes/22intervals/. You can construct it in `O(n log n)`, and you can query `n` items in `n log n`. You might be able to walk it in `O(n)`, though. — Jim Mischel, Oct 31 '11 at 21:16
To compare every object with every other is a simple nested loop. Look into selection sort. That will work well if your number of ranges is relatively small. — Jim Mischel, Oct 31 '11 at 21:17
This may be helpful http://stackoverflow.com/questions/7438404/how-to-get-overlap-range-of-two-range (especially the second answer) — hatchet - done with SOverflow, Oct 31 '11 at 21:18

hugomg · Accepted Answer · 2011-10-31T23:42:41.997

0

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

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

edited Oct 31 '11 at 23:42

answered Oct 31 '11 at 21:02

hugomg

68,213
24
160
246

Unless I'm misunderstanding, this is the "selection sort" method, right? Compare each range with all ranges below it, with an early out testing start time against curr_end. – Jim Mischel Oct 31 '11 at 21:09
I don't quite understand this, could you explain a bit better? you are using a stack. =\ Oh, and I should say the indexes are as important, as this is actually an array of objects that have a start and end index. I'll update my question, as it is relevant. – NullVoxPopuli Oct 31 '11 at 21:10
ehm.. not quite. you have too keep the biggest `.end`, otherwise you can miss intersections. – Karoly Horvath Oct 31 '11 at 21:22
is this the most efficent way to do this? i mean, it looks like O(n^n) – NullVoxPopuli Nov 01 '11 at 13:18
It looks O(n) to me. You start with i=0 and i goes up to N one by one. (note how each array element is processed only once) – hugomg Nov 01 '11 at 13:21

How do I write a method that finds all the intersections in an array of ranges?

1 Answers1