Слияние диапазонов в C ++

Question

У меня есть список случайно упорядоченных уникальных закрытых диапазонов R ₀ ... R _n-1 , где

R _i = [r1 _i , r2 _i ] (r1 _i <= r2 <sub>i )

Впоследствии некоторые диапазоны перекрываются (частично или полностью) и, следовательно, требуют объединения.

У меня вопрос: какие алгоритмы или методы лучше всего использовать для объединения таких диапазонов. Примеры таких алгоритмов или ссылок на библиотеки, которые выполняют такую ​​операцию слияния, были бы великолепны.

Answer 1

Что вам нужно сделать, это:

1. Сортировка элементов лексикографически, где ключом диапазона является [r_start, r_end]

2. Переберите отсортированный список и проверьте, перекрывается ли текущий элемент со следующим. Если это расширяет текущий элемент, чтобы быть r [i] .start, r [i + 1] .end, и перейти к следующему элементу. Если он не перекрывается, добавьте текущий в список результатов и перейдите к следующему элементу.

Вот пример кода:

    vector<pair<int, int> > ranges;
    vector<pair<int, int> > result;
    sort(ranges.begin(),ranges.end());
    vector<pair<int, int> >::iterator it = ranges.begin();
    pair<int,int> current = *(it)++;
    while (it != ranges.end()){
       if (current.second > it->first){ // you might want to change it to >=
           current.second = std::max(current.second, it->second); 
       } else {
           result.push_back(current);
           current = *(it);
       }
       it++;
    }
    result.push_back(current);

Answer 2

Boost.Icl может быть полезно для вас.

Библиотека предлагает несколько шаблонов, которые вы можете использовать в вашей ситуации:

• interval_set - Реализует набор как набор интервалов - объединяет смежные интервалы.
• Отдельный_интервал_сет - реализует набор как набор интервалов, оставляя соседние интервалы отдельными
• split_interval_set - реализует набор как набор интервалов - при вставке интервалы перекрытия делятся

Существует пример для слияния интервалов с библиотекой:

interval<Time>::type night_and_day(Time(monday,   20,00), Time(tuesday,  20,00));
interval<Time>::type day_and_night(Time(tuesday,   7,00), Time(wednesday, 7,00));
interval<Time>::type  next_morning(Time(wednesday, 7,00), Time(wednesday,10,00));
interval<Time>::type  next_evening(Time(wednesday,18,00), Time(wednesday,21,00));

// An interval set of type interval_set joins intervals that that overlap or touch each other.
interval_set<Time> joinedTimes;
joinedTimes.insert(night_and_day);
joinedTimes.insert(day_and_night); //overlapping in 'day' [07:00, 20.00)
joinedTimes.insert(next_morning);  //touching
joinedTimes.insert(next_evening);  //disjoint

cout << "Joined times  :" << joinedTimes << endl;

и вывод этого алгоритма:

Joined times  :[mon:20:00,wed:10:00)[wed:18:00,wed:21:00)

А вот о сложности их алгоритмов:

Сложность времени сложения

Answer 3

O (n * log (n) + 2n):

• Сделать отображение r1_i -> r2_i,
• QuickSort на r1_i,
• пройдитесь по списку, чтобы выбрать для каждого r1_i -значения наибольшее r2_i -значение,
• с этим r2_i -значением, которое вы можете пропустить по всем последующим r1_i меньше, чем r2_i

Answer 4

Простой алгоритм будет выглядеть следующим образом:

• Сортировка диапазонов по начальным значениям
• Перебор диапазонов от начала до конца и всякий раз, когда вы обнаружите диапазон, который перекрывается со следующимодин, объединить их

Answer 5

Ответ Джетро содержит ошибку. Должно быть

if (current.second > it->first){
    current.second = std::max(current.second, it->second);        
} else { 

Answer 6

Мой алгоритм не использует дополнительное пространство и также легок. Я использовал 2-pointer подход. «i» продолжает увеличиваться, в то время как «j» отслеживает текущий элемент, который обновляется. Вот мой код:

bool cmp(Interval a,Interval b)
 {
     return a.start<=b.start;
 }
vector<Interval> Solution::insert(vector<Interval> &intervals, Interval newInterval) {
    int i,j;
    sort(intervals.begin(),intervals.end(),cmp);
    i=1,j=0;
    while(i<intervals.size())
    {
        if(intervals[j].end>=intervals[i].start)  //if overlaps
        {
            intervals[j].end=max(intervals[i].end,intervals[j].end); //change
        }
        else
        {
            j++;
            intervals[j]=intervals[i];  //update it on the same list
        }
        i++;
    }
    intervals.erase(intervals.begin()+j+1,intervals.end());
    return intervals;
}

Интервал может быть общедоступным классом или структурой с элементами данных «начало» и «конец». Удачного кодирования:)