查找一组间隔的覆盖范围

Question

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

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

或者，我们可以使用 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)。

space也是线性的。

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

P.S。我还没有完全测试代码，但它似乎有效。

查找一组间隔的覆盖范围

Find coverage of a set of intervals

algorithm

intervals