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