algorithm - 查找一组间隔的覆盖范围

Question

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

我最初的方法是迭代一组间隔；将每个间隔中的数字添加到排序链接列表中。如果排序列表中已经存在任何数字，则跳过它。我相信这需要 O(N^2) 时间并消耗 O(N) 空间，所以我们可能会做得更好。

或者，我们可以使用 Interval BST .然而，这似乎主要用于查明是否存在与给定间隔的重叠(需要 O(lgn))。找到它的覆盖范围似乎又需要 O(n^2)。我们能做得比 O(n^2) 更好吗？

Answer 1

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

排序后你会得到:{<-2, 2>, <1,3>, <9, 9>}。

排序将花费 O(NlogN)。

现在创建一个变量 sum = 0。

然后设置 L = (1).left 和 R = (1).right。

线性遍历所有保持你遇到的最大 R 的东西，直到 R < (k).left，然后做 sum += abs(L - R) + 1 并按照刚刚描述的那样继续其余的事情。这大约需要 O(N)。所以，一共:O(NlogN + N) ~ O(NlogN)。

空间也是线性的。

#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;
}

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