# Algorithm to find span intersections in a sorted set

I have a set of items strictly ordered on time. Each item can either be single (no Next, no Previous) or part of a span (with either 1 or 2 further endpoints). For example in the picture A is part of a 3 element span 1 -> 4 -> 5, B is part of a 2 element span 2 -> 3 and C is part of a 2 element span 6 -> 16. As you can see, spans can overlap each other (start2 > start1, end1 > end2).

What I want to do is work out a fast algorithm for finding which spans (or individuals) are intersecting a given span Min -> Max.

My naive approach is to simply test every single item in the set, with something like:

``````for(auto const & e : items)
{
if(e.Previous)
{
// Middle or last item in a set (already been tested).

continue;
}

auto t1 = e.Time, t2 = e.Time;

if(e.Next)
{
if(e.Next.Next)
{
// Part of a 3 item span (start, middle, end).

t2 = e.Next.Next.Time;
}
else
{
// Part of a 2 item span (start, end).

t2 = e.Next.Time;
}
}

if(t1 > MaxTime || t2 < MinTime)
{
// Does not intersect the span.

continue;
}

... Do something with the item, such as draw it.
}
``````

This doesn't perform too badly with 250,000 items actually but starts to be pretty slow when you get into millions.

I have plenty of time available at start-up to get a std:future up and running to pre-process these things into some more useful structure if that helps. I also need to be able to append to the end of the set, though keeping strictly ascending time order (i.e. now() >= items.last().time).

Does anything occur to anyone?

• Are your times times or could they be used as index values as in your example? Mar 22, 2016 at 14:59
• If you partition the set into N sections, where N is some time span T (an hour, say), you could use the time as a hash, yes (integer divide by T). Then you can only consider buckets in the hash that intersect T. The trouble is many items won't be in the buckets considered because their start is in a bucket < Min or the end in a bucket > Max (I tried this). I'd need to put the interval into all intermediate buckets between start and end. Then my problem is how to avoid considering an item twice. Mar 22, 2016 at 15:17
• Do you check one min-max range or do you have a list of ranges to check? For only one range your algorithm seems OK. Mar 22, 2016 at 15:28
• Maybe you are faster if you structure your items in sets. These sets could have a start and endtime and you can check for intersection only using 2 values per set (Should be (Min < Start < Max || Min < End < Max || (Start < Min && Max < End)). Depending on how often you check and how large your sets are this might make a huge difference, Mar 22, 2016 at 15:45
• Just one range Carra. Simon that's not a bad idea actually. Partition the data so that all items are inside a set. It's very unlikely to be continuous over time, i.e. there will always be gaps where there are no spans. A quick pass through could work out some kind of optimal sectioning. Mar 22, 2016 at 15:47