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

[Igors]

Добрый день

Нужно написать ф-цию собирающую диапазоны в порядке возрастания и объединяющую если они перекрываются

Код

C++ (Qt)
using TPair = std::pair<int, int>;
 
void AddRange( std::vector<TPair> & dst, const TPair & p )
{
...
}

Как для новой пары(p) так и для всех эл-тов вектора гарантируется first <= second. Примеры

( {1, 2}, {8, 9 } } + {5, 5} =  ( {1, 2}, {5, 5}, {8, 9 } } // перекрытий нет
( {1, 2}, {8, 9 } } + {5, 7} =  ( {1, 2}, {5, 9 } }           // объединение

Ну и задача-максимум - то же для пар double, может даже удастся обобщить темплейтами. Конечно было бы замечательно "воспользоваться готовым", но где ж взять 

Спасибо

[RedDog]

С вектором "в лоб" решается, тупым пробегом итератором и сравнением по std::pair::first.
Дальше сравнение по std::pair::second и логика "слияния".
С double через задание точности, с какой точностью должны диапазоны пересекаться

[ssoft]

Используйте для поиска в упорядоченном векторе функции алгоритмов https://en.cppreference.com/w/cpp/algorithm/equal_range, а далее решайте, что следует сделать - изменить значение по одному из итераторов или вставить значение в контейнер.

[Igors]

С вектором "в лоб" решается, тупым пробегом итератором и сравнением по std::pair::first.
Дальше сравнение по std::pair::second и логика "слияния".
С double через задание точности, с какой точностью должны диапазоны пересекаться

Зачем тупой пробег если есть хотя бы lower_bound? Ну и тема посвящена "логике слияния", т.е. это совсем не "известная деталь/подробность". Задание точности для double - другая задача, здесь об этом речь не идет, напр пары

{ 5.0,  6.0 } + { 5.5,  9.0 }

пересекаются при любой точности

Используйте для поиска в упорядоченном векторе функции алгоритмов https://en.cppreference.com/w/cpp/algorithm/equal_range, а далее решайте, что следует сделать - изменить значение по одному из итераторов или вставить значение в контейнер.

Наверно Вы имели ввиду получить диапазон всех пар пересекающих вставляемую. Это особо ничего не экономит, а проверяет все эл-ты (в отличие от lower_bound). И если диапазон пуст - куда вставлять?

Ну в общем, так понимаю - в std готового нет. Я не удивлен, наверно такой алгоритм для std слишком сложен А вот с (пресловутыми) template интересно. Стали бы Вы обобщать?
Заметим что логика слияния различна

{ 5,  6 } + { 7,  8 } = { 5, 8 }
{ 5.0,  6.0 } + { 7.0,  8.0 } = { { 5.0,  6.0 }, { 7.0,  8.0 } }

Ой! Совсем забыл - есть же еще ИИ!!! 

[Авварон]

Я не удивлен, наверно такой алгоритм для std слишком сложен

https://leetcode.com/problems/merge-intervals/

да, оч сложно, задачка уровня medium

[RedDog]

Зачем тупой пробег если есть хотя бы lower_bound?

А он как то по другому в векторе найдет?

[Old]

А он как то по другому в векторе найдет?

Вектор отсортирован же. Конечно найдет по другому.

[Igors]

да, оч сложно, задачка уровня medium

Не понял, а писать бум или уже готовое нашли? 

[Авварон]

да, оч сложно, задачка уровня medium

Не понял, а писать бум или уже готовое нашли? 

я уже писал, хз

[ssoft]

Поиграйте с таким примером

Код

C++ (Qt)
#include <algorithm>
 
using Interval = ::std::pair< int, int >;
using Intervals = ::std::vector< Interval >;
 
// условие упорядочивания по значению начала диапазона
struct IntLowerCompare { bool operator () ( const Interval & left, const Interval & right )
{
    return left.second + 1 < right.first; }
};
 
// условие упорядочивания по значению конца диапазона
struct IntUpperCompare { bool operator () ( const Interval & left, const Interval & right )
{
    return left.first + 1 < right.second; }
};
 
// условие необходимости слияния
struct IntMergeCondition { bool operator () ( const Interval & left, const Interval & right )
{
    return left.second + 1 >= right.first; }
};
 
template < typename Intervals, typename Interval, typename LowerCompare, typename UpperCompare, typename MergeCondition >
void add ( Intervals & intervals, const Interval & interval, LowerCompare lower_compare, UpperCompare upper_compare, MergeCondition merge_condition )
{
    // итератор для первого значения в коллекции с возможно пересекающимся интервалом
    auto lower_iter = ::std::lower_bound( ::std::begin( intervals ), ::std::end( intervals ), interval, lower_compare );
    if ( lower_iter != ::std::end( intervals ) )
    {
        // если есть пересечение
        if ( merge_condition( interval, *lower_iter ) )
        {
            // итератор для последнего значения в коллекции с возможно пересекающимся интервалом
            auto upper_iter = ::std::upper_bound( ::std::begin( intervals ), ::std::end( intervals ), interval, upper_compare );
 
            auto first_iter = lower_iter;
            auto last_iter = upper_iter == ::std::end( intervals )
                ? lower_iter
                : upper_iter;
 
            // изменение пересекающегося
            lower_iter->first = ::std::min( first_iter->first, interval.first );
            lower_iter->second= ::std::max( last_iter->second, interval.second );
 
            // удаление лишних
            intervals.erase( ++first_iter, ++last_iter );
        }
        else
        {
            // вставка в середину
            intervals.insert( lower_iter, interval );
        }
    }
    else
    {
        // вставка в конец
        intervals.insert( lower_iter, interval );
    }
}
 
int main ( int, char ** )
{
    Intervals intervals = {{1, 2}, {8, 9 }};
    add( intervals, Interval{ -2, -1 }, IntLowerCompare{}, IntUpperCompare{}, IntMergeCondition{} );
    add( intervals, Interval{ 5, 5 },  IntLowerCompare{}, IntUpperCompare{}, IntMergeCondition{} );
    add( intervals, Interval{ 5, 7 }, IntLowerCompare{}, IntUpperCompare{}, IntMergeCondition{} );
    add( intervals, Interval{ 3, 7 }, IntLowerCompare{}, IntUpperCompare{}, IntMergeCondition{} );
    add( intervals, Interval{ 0, 10 }, IntLowerCompare{}, IntUpperCompare{}, IntMergeCondition{} );
    add( intervals, Interval{ 11, 11 }, IntLowerCompare{}, IntUpperCompare{}, IntMergeCondition{} );
}
 

[Igors]

Поиграйте с таким примером

Работает, с double не проверял, но верю. Все-таки этажерка из 3 хвункторов воспринимается тяжело. Хотя это общая проблема темплейтов. Пока "в теме" и это интересно - вроде ничего. Но если подзабыл, а особенно "не сам писал" - понять "замысел обобщения" трудно.

У меня так получилось (аттач). Смысл такой

Код

C++ (Qt)
auto it1 = std::lower_bound(beg, end, TPair(p.first, p.first));
auto it2 = std::lower_bound(beg, end, TPair(p.second, p.second));

В обоих случаях может "слиться" или найденный или предыдущий, ну или никакой.

Да, и посоветуйте как (красиво) избежать "first" и "second", напр массив вместо пары

Спасибо