Java algorithm for find intersection between intervals

Question

I have a time interval like this:

[5,10]

and I have more list of time point, with different length, for example:

t1=[3,6,9,10] 
t2=[2,4,5,6,10]
..

where in t1 [3,6] is the first interval, [6,9] the second and so on.

Same thing for t2 and other list.

Now I need to save the list, and the specific interval, that intersect with first time interval. For example in t1 I have [3,6] that intersect on [5,10], [6,9] that intersect with [5,10], etc.

I have made an algorithm but I work with more data and I need a fast algorithm. For example if I work with 300.000 list and every list have 200 time points my algorithm 1 fine in about 5-10sec. But if I have 10.000 or more time point the algorithm is very slow.

My algorithm is like this:

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: Yes I have ordered list.

Edit2: I have another problem, when i find the intersaction i need to calclulate a score between 0 and 1 of how the intersection is large. I use this:

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

I can speed up this too?

Answer 1

The intersection of two intervals [s1, s2] and [t1, t2] is empty if and only if:

    t2 < s1 or s2 < t1

So for two intervals to check if the two are intersecting or not you need to do only the test above.

Also once you know that s2 < t1 then there is no point to continue further on the list that brought t1 since the larger intervals will never intersect, which means you should move on.

Naive Psuedo Algorithm:

   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()

This can be improved quite a bit to really use the fact that [t1, t2, .. , t(n)] is sorted.

first note that [s1, s2] will intersect with [t(x), t(x+1)] iff t(x+1) >= s1 and s2 >= t(x)

However

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

also

if s2 >= t(x) then for every h>0  `s2 >= t(x-h)`

so if we find the smallest i so that t(i+1)>=s1 then all the intervals from [t(i), t(i+1)] on-wards meet the first condition of intersection; i.e. ([t(i+1), t(i+2)] , [t(i+2), t(i+3)] ...)

and if we find the largest j so that s2 >= t(j-1) then all the intervals from [t(j-1), t(j)] backwards meet the second condition . i.e. ([t(j-2), t(j-1)], [t(j-3), t(j-2)] ...)

All the intervals between i and j meet both criteria and only them.

So the final algorithm is:

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.       

Since {t1, t2, t3...t(n)} is sorted we can use binary search to find the indices i and j efficiently

EDIT2:

The intersection of [s1,s2] and [t1, t2] is:
[max(s1, t1), min(s2,t2)]

the sizes are: L1 = s2-s1 L2 = t2-t1 L3 = min(s2,t2) - max(s1,t1)

The score you are looking for is: L3/ min(L2, L1) a score between 0 and 1.

(min(s2,t2) - max(s1,t1)) / ( min(s2-s1, t2-t1) )

The cost of calculating this is 3 tests, 3 minus operations and one floating point operation. But I am assuming the intervals are valid and the intersection exists otherwise more tests are needed. (s2>s2, t2>t1 and min(s2,t2) > max(s1,t1). The final test is the same iff condition for intersection from the discussion above.