查找一组间隔的覆盖范围

Question

很久以前，我在准备面试时遇到了这个问题，认为这是一个需要解决的有趣问题。问题是这样的：找到一组区间的覆盖范围例如-给定[1,4）、[-2,3）、[9,10）：输出应该是7（区间集覆盖-2,-1,0,1,2,3,9)。

我最初的方法是迭代区间集；将每个间隔中的数字添加到已排序的链表中。如果排序列表中已存在任何数字，请跳过它。我相信这需要O（N^2）时间和O（N）空间，所以我们可能会做得更好。

或者，我们可以使用间隔BST。然而，这似乎主要用于确定是否与给定间隔重叠（需要O（lgn））。找到它的覆盖范围似乎需要再次进行O（n^2）。我们能做得比O（n^2）更好吗？

Answer 1

您可以将它们视为成对的，并按第一个元素对它们进行排序。

排序后，您将有：{

排序将需要O（NlogN）。

现在做一个变量sum=0。

然后设置L=（1）。左，R=（1）。右。

线性遍历所有对象，保持遇到的最大R直到R

空间也是线性的。

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;
typedef pair<int, int> pii;

int main() {
    int l, r;
    vector<pii> pairs;
    while (cin >> l >> r) {
        pairs.emplace_back(l, r);
    }
    pairs.emplace_back(INT_MAX, INT_MAX); // sentinel
    sort(pairs.begin(), pairs.end(), 
    [](const pii& x, const pii& y) { return x.first < y.first; });

    auto p_one = pairs.begin(), p_two = pairs.begin() + 1;
    int L = p_one->first;
    int R = p_one->second;
    int sum = 0;
    while (p_two != pairs.end()) {
        if (R < p_two->first) {
            sum += abs(L - R) + 1;
            L = p_two->first;
            R = INT_MIN;
        }
        p_one++; p_two++;
        if (p_one->second > R) R = p_one->second;
    }
    cout << sum;
}

附言：我还没有完全测试代码，但它似乎有效。