C++ 在一组区间内有效搜索值

Question

假设我有一组由 [min, max] 对描述的间隔。我想找到包含给定值的所有间隔集。

我制作了这个在 O(n) 时间内有效的解决方案，并作为我所追求的示例:

#include <iostream>
#include <vector>

using namespace std;

struct data
{
    int minValue;
    int maxValue;
};

void searchValue(const vector<data> &v, int target)
{
    for(size_t i = 0; i < v.size(); i++)
    {
        if(target >= v[i].minValue && target <= v[i].maxValue)
            cout << "Found target at set " << i << " (" << v[i].minValue << "," << v[i].maxValue << ")" << endl;
    }
}

int main()
{
    data d1 = {-1, 0};
    data d2 = {0, 3};
    data d3 = {-1, 5};
    data d4 = {10, 11};
    data d5 = {9, 12};

    // Vector to hold the interval sets
    vector<data> v{d1, d2, d3, d4, d5};

    // Search for the interval sets which contain the number 2
    searchValue(v, 2);

    return 0;
}

找到所有可能的集合非常重要，而不仅仅是一个。

我现在正在寻找一种计算效率更高的解决方案，可能在对数时间内。我认为可能有 multiset/multimap、lower_bound/upper_bound 等的解决方案，但到目前为止我还没有成功。

这可以使用区间树来实现，但我相信可能有一个仅使用 STL 的解决方案。

Answer 1

使用STL似乎很难。

你可以使用区间树:

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

Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.