поиск наибольшего подмножества интервалов

Я пытался решить эту проблему здесь.

Кроме того, размещение вопроса: Вам дан список из N интервалов. Задача состоит в том, чтобы выбрать наибольшее подмножество интервалов так, чтобы никакие три интервала в подмножестве не имели общей точки?

но не мог прийти к решению. Это то, что я пробовал до сих пор:

  1. ДП: не думаю, что у проблемы есть перекрывающиеся подзадачи, так что это не сработало
  2. свел его к графу, где каждая точка является вершиной, а интервалы — ребрами неориентированного графа. Тогда задача сводится к поиску непересекающихся путей максимальной длины в графе. Не смог придумать аккуратный способ сделать это, а также
  3. попытался уменьшить его до сетевого потока, но это тоже не сработало.

Не могли бы вы, ребята, дать мне подсказки о том, как подойти к этой проблеме, или если я что-то упустил. Извините, я занимаюсь алгоритмами после очень долгого времени и в последнее время не на связи.


algorithm puzzle
person user352951    schedule 31.05.2012    source источник
comment
Звучит как работа для дерева сегментов.   -  person Justin    schedule 31.05.2012
comment
Это похоже на проблему с расписанием.   -  person NominSim    schedule 31.05.2012

Ответы (2)


arrow_upward
3
arrow_downward

Я дам решение в общих словах, не программируя его.

Обозначим сегменты как s1, s2, ..., sn. Их начало как b1, b2,... bn, а их конец как e1, e2,... en.

Отсортируйте сегменты по их началу, поэтому b1‹ b2‹...‹ bn. Достаточно проверить их, если не выполняется условие отсутствия трех отрезков, покрывающих точку. Мы будем делать это в порядке от b1 до bn. Итак, начнем с b1, перейдем к следующей точке и так далее по порядку, пока в какой-то точке bi не окажется три отрезка, покрывающих ее. Это будет отрезок si и два других, скажем, sj и sk. Из этих трех сегментов удалите один с максимальной конечной точкой, т. е. max{ei, ej, ek}. Перейдите к началу следующего сегмента (bi+1). Когда мы достигнем bn, процесс завершится. Все оставшиеся отрезки составляют наибольшее подмножество отрезков, такое что никакие три отрезка не имеют общей точки.

Почему это будет максимальное подмножество. Допустим, наше решение — это S (набор сегментов). Предположим, что существует оптимальное решение S*. Снова отсортируйте сегменты в S и S* по координате их начала. Теперь мы пройдемся по отрезкам в S и в S* и сравним их конечные точки. По построению S для любого k-го сегмента в S его конечная координата меньше, чем конечная координата k-го сегмента в S* (ek‹=ek). Следовательно, количество отрезков в S не меньше, чем в S (двигаясь по S*, мы всегда обгоняем S).

Если это недостаточно убедительно, попробуйте сначала подумать о более простой задаче, в которой никакие два сегмента не могут пересекаться. Решение такое же, но гораздо более интуитивно понятно, почему оно дает правильный ответ.

person shalabuda    schedule 31.05.2012
comment
хорошо, поправьте меня, если я ошибаюсь, но скажем, если у меня есть эти сегменты (1-2), (1-3), (1-10), (3-5), (3-6), то в соответствии с этим алгоритм решение должно быть (1-2), (1-3), (3-5), но лучшим решением может быть (1-10), (1-2), (3-5) (3-6) - person user352951; 01.06.2012
comment
@ user352951 в вашем примере (1-10), (3-5) и (3-6) перекрываются - person shalabuda; 01.06.2012

arrow_upward
2
arrow_downward

Шафа прав;

#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;
}
person GlacierKba6    schedule 23.09.2012