计算与给定区间集相交的最小整数集

Question

给定一组（有限的）区间 [a_i, b_i]，其中 a_i <= b_i 是整数，我想要一个算法来计算与每个区间相交的最小（基数）整数集 C。

为了防止某些读者被上面的区间符号分散注意力，这个问题不是关于非整数的。

如果这是一个已知问题，即使它是一个 NP 完全问题，了解它也会很有用。

Answer 1

好吧，这不是我的想法，但对我来说看起来很合理。

我们有一组 'intervals'。 Is 中的每个 I 是 { N in N | a<=n<=b}。我们想要整数集 C，这样对于 Is 中的所有 I，C 中有 c，I 中有 c，实际上我们想要最小基数的 C

a/ 假设Is中的I是[a,a]。那么我们必须在C中有一个。所以让

C0 = {a in N | [a,a] in Is}
Is1 = { I in Is | for all c in C0, c not in I }

如果我们能找到 Is1 的解 C1，C0 并集 C1 就是 Is 的解

b/ 让我在是假设

Js = { J in Is | I subset J }.

那我们就可以把Js都扔掉了。因为如果 C 是 Is\Js 的解，那么因为 C 中有一个 c，I 中有 c，那么对于 Js 中的所有 K，K 中有 c，所以 C 是 Is 的解。

要实现这一点，请先按 a 然后按 b 排序。假设 I 是最小元素，J 是它的后继元素。如果 a(I)==a(J) 那么我们必须有 b(I)<=b(J) 所以我子集 J，我们扔掉 J，然后继续考虑 I 和 J 的后继者如果 a(I)

在此之后，对于 Is 中的每个 I 和后继 J，

a(I) < a(J) and b(I) < b(J).

如果Is现在只是一个区间，我们选择Is中唯一元素的任意一个元素停止

设I为Is中的最小区间，令

Js = { J in Is | a(J)<=b(I)}.

如果 Js 为空，我们选择 I 的任何元素，从 Is 中删除 I 并继续。

否则设k = b(I)。然后 k 在 I 中；如果 J 在 J 中那么

a(j)<=b(I)<b(J)

所以 k 在 J 中。此外，对于 J != I 和 J 不在 Js 中，I 和 J 是不相交的，因此 I 中的元素不能比 k 中的元素更多。我们将 k 添加到 C，从 Is 中删除 I 和 Js，然后继续。

Answer 2

这是一个 O(n logn) 的解决方案。

第一步是对区间进行排序，根据末尾的值b。

然后，对于根据此顺序考虑的每个间隔，添加相应的 b 值，但前提是此间隔尚未与点相交。这可以通过将其 a 参数的值与最后选择的 b 点的值进行比较来简单地检查。

第二步的复杂度为 O(n)。然后整体复杂度由排序复杂度O(n logn)决定。

这里有一个简单的C++实现来说明算法的简单性。

输出：

Intervals before sorting: [2, 4] [0, 3] [6, 7] [3, 3] [3, 5]
Intervals after sorting: [0, 3] [3, 3] [2, 4] [3, 5] [6, 7]
set of points: 3 7

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Interval {
    int a, b;
    friend std::ostream& operator << (std::ostream& os, const Interval& x) {
        os << '[' << x.a << ", " << x.b << ']';
        return os;
    }
    friend bool operator< (const Interval& v1, const Interval& v2) {return v1.b < v2.b;}
};

template <typename T>
void print (const std::vector<T> &x, const std::string& str = "") {
    std::cout << str;
    for (const T& i: x) {
        std::cout << i << " ";
    }
    std::cout << "\n";
}

std::vector<int> min_intersection (std::vector<Interval>& interv) {
    std::vector<int> points;
    std::sort (interv.begin(), interv.end());
    print (interv, "Intervals after sorting: ");    
    if (interv.size() == 0) return points;
    int last_point = interv[0].a - 1;
    for (auto& seg: interv) {
        if (seg.a <= last_point) continue;
        last_point = seg.b;
        points.push_back (last_point);
    }
    return points;
}

int main() {
    std::vector<Interval> interv = {{2, 4}, {0, 3}, {6, 7}, {3, 3}, {3, 5}};
    print (interv, "Intervals before sorting: ");
    auto points = min_intersection (interv);
    print (points, "set of points: ");
    return 0;
}

计算与给定区间集相交的最小整数集

compute a minimal set of integers which intersects a given set of intervals

algorithm

integer

intersection

cluster-analysis