求最大区间子集

Question

我正试图解决这个问题，这里。

同时，发布问题:给你一个N个间隔的列表。所面临的挑战是选择最大的区间子集，使子集中没有三个区间共享公共点？

但没能找到解决办法。这就是我迄今为止尝试过的：

1. DP:不要认为问题有重叠的子问题，所以这是行不通的。
2. 将其简化为一个图，其中每个点为顶点，区间为无向图的边。然后，问题归结为在图中找到最大长度不相交的路径。也想不出一个很好的方法
3. 试着把它减少到网络流，但这也不起作用。

你们能给我一些关于如何处理这个问题的提示吗?或者如果我遗漏了什么。对不起，我已经做了很长一段时间的算法了，最近我已经失去联系了。

Answer 1

沙法是对的；

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