0
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – David Richerby Dec 12 '18 at 16:58
  • $\begingroup$ Note that "Please write some code for me" questions are off-topic on Stack Exchange, so I've deleted the database-vs-Java part. $\endgroup$ – David Richerby Dec 12 '18 at 16:58
  • $\begingroup$ @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. $\endgroup$ – Keith C Dec 12 '18 at 17:05
  • $\begingroup$ Please credit the original source of the problem. $\endgroup$ – John L. Dec 12 '18 at 18:05
  • 1
    $\begingroup$ @Apass.Jack Thanks for taking the time to explain. I'll add to the question. $\endgroup$ – Keith C Dec 12 '18 at 19:52
1
$\begingroup$

Your question is not clear.

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

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Following VK1's link reveals a further link to:

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

that seems like a better match to the problem as the date ranges are not consecutive so there are gaps. A quick Google reveals and implementation too:

https://github.com/charcuterie/interval-tree/blob/master/src/datastructures/IntervalTree.java

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.