c++ - 在给定范围内查找对值

Question

我有一个数组或 N 对 (v1, v2)其中 v1 <= v2 .这些应该代表从 v1 开始的时间事件。结束于 v2 .它们可以相等，则事件是瞬时的。该数组按开始时间排序，v1 .

对于给定范围 (L, R) , 我想找到任何一对 L <= v1 <= R or 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，因为它是当前唯一运行的。

Answer 1

由于您需要处理三种情况 - 在给定范围内开始、发生或结束，我们可以将其分为三个部分。

1. 开始:v1在于 [L,R] .
2. 结尾:v2在于 [L,R] .

第三种情况可以表述为v1 <= R and L <= v2 , 但前两种情况部分涵盖了这种情况，因此我们将使用不同的公式来避免冲突:

1. 发生:v1 < L and R < v2

好吧，如果我们可以按 v1 对事件数组进行排序，则很容易处理对数加报告事件数时间的第一种情况。 .同样的技巧适用于第二种情况。

第三种情况比较棘手。让我们画画:

粉色区域代表所有区间L <= R .红点是一个区间，绿色区域代表我们想要捕获的所有可能事件。要进行这样的捕获，可以使用 k2-tree .