如何使用set获取索引是否存在于哪个区间<pair<int, int>>

Question

我有

std::set<std::pair<int, int>> intervals

，它的值是一些间隔，它与此类似：

{ 0, 5 },
{ 5, 8 },
{ 8, 10 }

我有一个数字

x

我可以找到它在哪个区间使用

lower_bound

或

upper_bound

吗？

我需要一个具有

O(log(N))

复杂性的解决方案。

因为我记得我看到有人这样做：

int x;
std::set<std::pair<int, int>> intervals;
cin >> x;
auto ans = intervals.upper_bound({ x, INF })

我不记得

INF

的价值是什么

注意：间隔不相交。

Answer 1

首先，如果您想要一组连续的范围，您应该简单地将它们表示为仅保留每个范围的开头的集合。

set<int> boundaries { 0, 5, 8, 10 };

如果您确实想使用保留范围两端的结构，则以下内容将允许您在

O(log(N))

中进行搜索。在保留两端的情况下，可以表达除连续范围设置之外的其他内容，因此本例有意省略[6, 8)。如果该结构保留两端，也可以表达重叠的范围集。在这种情况下，我们将不得不搜索多个范围。我忽略了那个例子。

#include <algorithm>
#include <limits>
#include <numeric>
#include <set>

using namespace std;
int main()
{
    set<pair<int, int>> intervals{ { 0, 5 },
                                   { 5, 6 },
                                   { 8, 10 } }; // drop {6, 8} version.
    {
        constexpr auto INF = numeric_limits<int>::max();
        auto find = [&](const int x) {
            auto next = intervals.upper_bound({ x, INF });
            if (next != intervals.begin()) {
                if (auto ans = prev(next); x < ans->second)
                    return ans;
            }
            return intervals.end();
        };
        for (int x = -1; x <= 11; ++x) {
            if (auto ans = find(x); ans != intervals.end()) {
                printf("%d is in [%d, %d)\n", x, ans->first, ans->second);
            } else {
                printf("%d is not in any range\n", x);
            }
        }
    }

    set<int> boundaries{ 0, 5, 8, 10 };
    {
        auto find = [&](const int x) {
            auto next = boundaries.upper_bound(x);
            if (next != boundaries.begin()) {
                return prev(next);
            }
            return boundaries.end();
        };

        for (int x = -1; x <= 11; ++x) {
            if (auto ans = find(x); ans != boundaries.end()) {
                if (auto nx = next(ans); nx != boundaries.end()) {
                    printf("%d is in [%d, %d)\n", x, *ans, *nx);
                } else {
                    printf("%d is in [%d, inf)\n", x, *ans);
                }
            } else {
                printf("%d is in [-inf, %d)\n", x, *boundaries.begin());
            }
        }
    }
}

标准输出在这里。

// == set<pair<int, int>>
-1 is not in any range
0 is in [0, 5)
1 is in [0, 5)
2 is in [0, 5)
3 is in [0, 5)
4 is in [0, 5)
5 is in [5, 6)
6 is not in any range
7 is not in any range
8 is in [8, 10)
9 is in [8, 10)
10 is not in any range
11 is not in any range

// == set<int>
-1 is in [-inf, 0)
0 is in [0, 5)
1 is in [0, 5)
2 is in [0, 5)
3 is in [0, 5)
4 is in [0, 5)
5 is in [5, 8)
6 is in [5, 8)
7 is in [5, 8)
8 is in [8, 10)
9 is in [8, 10)
10 is in [10, inf)
11 is in [10, inf)

Answer 2

在我看来，需要创建一个自定义结构/类，如下所示：

#include <iostream>
#include <set>

using namespace std;

struct Pair {
  int start, end;

  bool operator==(const Pair& p) const {
    return (start == p.start) && (end == p.end);
  }
  bool operator<(const Pair& p) const {
    return (start < p.start);
  }

  bool at(int y) const {
    if(y >= start && y < end)
      return true;
    else
      return false;
  }
};

int main()
{
  set<Pair> s = { {0,5}, {5,8}, {8,10}};

  for(auto& x: s) {
    if(x.at(6))
      cout << x.start << ":" << x.end << endl;
  }

  return 0;
}