mardi 27 août 2019

Finding pair values in a given range

I have an array or N pairs (v1, v2) where v1 <= v2. These are supposed to represent events in time that start at v1 and end at v2. they can be equal, then the event is instantaneous. The array is sorted by starting time, v1.

For a given range (L, R), I would like to find any pair where L <= v1 <= R or L <= v2 <= R. The idea here is to get events starting, happening or ending in the given range.

My main problem is efficiency. The array could contains hundreds of thousands of events. So just a linear search going through all pairs is not an option.

I read a bit about kd-tree but the problem with it is that it excludes the boundaries of the range and would only return L <= v1 <= R AND L <= v2 <= R. That is, would only return events that actually happen (start AND end) in the range whereas I need start OR end (or both obviously).

I thought also about keeping 2 lookup tables (I use double for time)

std::map<double, Event*> startPoints;
std::map<double, Event*> endPoints;

and the use the std::find algorithm in both of them and merge the results.

Just looking for an advise, wether it's a good solution or if there is a more clever way.

Aucun commentaire:

Enregistrer un commentaire