给定一个范围(L, R),我想找到任何一对满足L <= v1 <= R或L <= v2 <= R的值。这里的思路是获取在给定范围内开始、发生或结束的事件。
我的主要问题是效率。数组可能包含数十万个事件。所以只通过遍历所有对的线性搜索不是一个选择。
我了解过kd-tree,但它的问题是它排除了范围的边界,并且只返回L <= v1 <= R AND L <= v2 <= R。也就是说,只返回在范围内实际发生(开始和结束)的事件,而我需要开始或结束(或两者都有)。
我还考虑过保持2个查找表(我使用double作为时间)。
std::map<double, Event*> startPoints;
std::map<double, Event*> endPoints;
并在它们两者中使用std::find
算法,然后合并结果。
只是想寻求建议,无论这是否是一个好的解决方案,或者是否有更聪明的方法。
编辑:
重新考虑,这更加复杂。以下是预期结果的示例:
- L < R:范围足够大
|---Ev1---| |---Ev3---| |---Ev5---|
|---Ev2---| |---Ev4---|
| |
L R
在这里,我想获取发生在范围内的Ev2(结束于范围内),正在范围内发生的Ev3以及开始于范围内的Ev4。
- L < R:范围太小了,无法完整记录事件
|---Ev1---| |---Ev3---| |---Ev5---|
|---Ev2---| |---Ev4---|
| |
L R
我希望得到Ev3在其当前范围内的情况,以及Ev4在范围内启动时的情况。
- L == R:如果我想知道某个时间点会发生什么
|---Ev1---| |---Ev3---| |---Ev5---|
|---Ev2---| |---Ev4---|
|
LR
我只想选择Ev2,因为它是目前唯一在运行的。
L <= v1 <= R or L <= v2 <= R
,然后是开始、发生或结束,但这不一样。对于发生,你需要v1 <= R and L <= v2
。 - Yola