# Efficient way to find matching date ranges?

We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate set of 1000 of these. But a linear search is exponentially expensive.

So is there an algorithm that is more efficient? (For data related to a single date, using the date as the key of a hashmap works, but not much help when there is a pair of dates.)

(The source of the problem is my commercial work where there are a large number of date ranged payments that need to be matched with another large set of date ranged payments. And the environment the code runs in applies hard limits to how much CPU time can be consumed.)

• "linear search is exponentially expensive" Surely it can't be more than quadratically expensive? Worst case, you compare every one of the first batch of intervals with every one of the second. – David Richerby Dec 12 '18 at 16:58
• Note that "Please write some code for me" questions are off-topic on Stack Exchange, so I've deleted the database-vs-Java part. – David Richerby Dec 12 '18 at 16:58
• @DavidRicherby Ok sorry about that. Just to hinting that the set of date ranges can be pre-processed. Happy to write the code based on an algorithm documented. Yep sorry about the loose language - quadratically expensive is the problem. – Keith C Dec 12 '18 at 17:05
• Please credit the original source of the problem. – John L. Dec 12 '18 at 18:05
• @Apass.Jack Thanks for taking the time to explain. I'll add to the question. – Keith C Dec 12 '18 at 19:52

I am assuming you have 1000 date intervals in some set $$A$$ and another 1000 in set $$B$$ and you wish to find which intervals in $$B$$ lie completely inside some interval in $$A$$.

For an interval [x,y] in $$B$$, search points $$x$$ and $$y$$ in the segment tree built on $$A$$ and find sets that overlap.

Look up Segment tree.

Its stores line segments with starting point and end point. You can modify it to store start date and end date.

https://en.wikipedia.org/wiki/Segment_tree