algorithm - 找到区间的最大子集

Question

我试图在这里解决这个问题。

另外，发布问题：给你一个 N 个区间的列表。挑战是选择最大的区间子集，使得子集中没有三个区间共享一个公共点？

但无法找到解决方案。这是我到目前为止所尝试的：

1. DP：不要认为问题有重叠的子问题，所以这不起作用
2. 将其简化为一个图，每个点都是一个顶点，区间是无向图的边。然后问题减少到在图中找到最大长度的不相交路径。也想不出一个巧妙的方法来做到这一点
3. 尝试将其减少到网络流量，但效果不佳。

你们能否给我一些关于如何解决这个问题的提示，或者我是否遗漏了什么。对不起，我做了很长时间后才做算法，最近失去了联系。

Answer 1

我将在不编程的情况下用一般语言给出解决方案。

让我们将段表示为 s ₁ , s ₂ , ..., s _n。它们的开头为 b ₁ , b ₂ ,... b _n，结尾为 e ₁ , e ₂ ,... e _n。

按段的开头对段进行排序，因此 b ₁ < b ₂ <...< b _n。如果没有三个段覆盖一个点的条件成立，检查它们就足够了。我们将按照从 b ₁到 b _n的顺序执行此操作。因此，从 b ₁开始，移动到下一个点，以此类推，直到某个点 b _i有三个段覆盖它。这些将是段 s _i和另外两个段，比如说 s _j和 s _k。在这三个段中，删除具有最大端点的段，即 max{e _i , e _j , e _k}。移动到下一段的开头 (b _i+1 )。当我们到达 b _n时，这个过程就完成了。剩下的所有线段构成最大的线段子集，因此没有三个线段共享一个公共点。

为什么这将是最大子集。假设我们的解决方案是 S（段集）。假设存在最优解 S*。再次，按照起点坐标对 S 和 S* 中的段进行排序。现在，我们将遍历 S 和 S* 中的段并比较它们的端点。通过为 S 中的任何第 k 段构造 S，^其结束坐标小于S* 中第 k 段的结束坐标（^ek _< = _ek ）。因此，S 中的段数不少于 S（在 S* 中移动，我们总是超过 S）。

如果这还不够令人信服，请先尝试考虑一个更简单的问题，即没有两个片段可以重叠。解决方案是相同的，但更直观地了解为什么它给出了正确的答案。

Answer 2

沙法是对的；

#include <iostream>
#include <set>

using namespace std;

class Interval{
public:
int begin;int end;
Interval(){
    begin=0;end=0;
}

Interval(int _b,int _e){
    begin=_b;end=_e;
}

 bool operator==(const Interval& i) const {
     return (begin==i.begin)&&(end==i.end);
 }

 bool operator<(const Interval& i) const {
     return begin<i.begin;
 }
};

int n,t,a,b;
multiset<Interval> inters;
multiset<int> iends;

multiset<Interval>::iterator it1;
multiset<int>::iterator et1;

int main(){
scanf("%d",&t);
while(t--){
    inters.clear();
    iends.clear();
    scanf("%d",&n);
    while(n--){
        scanf("%d %d",&a,&b);
        Interval inter(a,b);
        inters.insert(inter);
    }
    it1=inters.begin();
    while(it1!=inters.end()){
        iends.insert(it1->end);
        et1=iends.lower_bound(it1->begin);
        multiset<int>::iterator t=et1;
        if((++et1!=iends.end())&&(++et1!=iends.end())){
            //把剩下的线段全部删掉
            while(et1!=iends.end()){
                multiset<int>::iterator te=et1;
                et1++;
                iends.erase(te);
            }
        }
        it1++;
    }
    printf("%d\n",iends.size());
}
system("pause");
return 0;
}