Take the 2-minute tour ×

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)

share|improve this question
What are you intersecting? –  Matt Fenwick Oct 31 '11 at 20:56
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
This may be helpful stackoverflow.com/questions/7438404/… (especially the second answer) –  hatchet Oct 31 '11 at 21:18
show 5 more comments

1 Answer

up vote 0 down vote accepted

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];

int i=0;
    Range curr = array[i];  //invariant: curr doesn't intersect with anyone befor it
    while(i < N && array[i].start <= curr.end){
        output that curr and array[i] intersect;
        if(array[i].end > curr.end){
            curr = array[i]
share|improve this answer
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
I updated the pseudo code to be more complete –  missingno Oct 31 '11 at 21:16
ehm.. not quite. you have too keep the biggest .end, otherwise you can miss intersections. –  Karoly Horvath Oct 31 '11 at 21:22
@yi_H: yes, I think I fixed it now –  missingno Oct 31 '11 at 23:45
show 2 more comments

Your Answer


