Russian Qt Forum

Программирование => С/C++ => Тема начата: Igors от Январь 25, 2022, 11:14



Название: Слияние диапазонов
Отправлено: Igors от Январь 25, 2022, 11:14
Добрый день

Нужно написать ф-цию собирающую диапазоны в порядке возрастания и объединяющую если они перекрываются
Код
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, может даже удастся обобщить темплейтами. Конечно было бы замечательно "воспользоваться готовым", но где ж взять  :)

Спасибо


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


Название: Re: Слияние диапазонов
Отправлено: ssoft от Январь 25, 2022, 23:31
Используйте для поиска в упорядоченном векторе функции алгоритмов https://en.cppreference.com/w/cpp/algorithm/equal_range (https://en.cppreference.com/w/cpp/algorithm/equal_range), а далее решайте, что следует сделать - изменить значение по одному из итераторов или вставить значение в контейнер.


Название: Re: Слияние диапазонов
Отправлено: Igors от Январь 26, 2022, 07:34
С вектором "в лоб" решается, тупым пробегом итератором и сравнением по 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 (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 } }

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


Название: Re: Слияние диапазонов
Отправлено: Авварон от Январь 26, 2022, 10:55
Я не удивлен, наверно такой алгоритм для std слишком сложен :)

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

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


Название: Re: Слияние диапазонов
Отправлено: RedDog от Январь 26, 2022, 11:25
Зачем тупой пробег если есть хотя бы lower_bound?
А он как то по другому в векторе найдет?


Название: Re: Слияние диапазонов
Отправлено: Old от Январь 26, 2022, 11:28
А он как то по другому в векторе найдет?
Вектор отсортирован же. Конечно найдет по другому. :)


Название: Re: Слияние диапазонов
Отправлено: Igors от Январь 27, 2022, 08:37
да, оч сложно, задачка уровня medium
Не понял, а писать бум или уже готовое нашли?  ???


Название: Re: Слияние диапазонов
Отправлено: Авварон от Январь 27, 2022, 17:23
да, оч сложно, задачка уровня medium
Не понял, а писать бум или уже готовое нашли?  ???

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


Название: Re: Слияние диапазонов
Отправлено: ssoft от Январь 28, 2022, 10:55
Поиграйте с таким примером

Код
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{} );
}
 


Название: Re: Слияние диапазонов
Отправлено: Igors от Январь 29, 2022, 11:24
Поиграйте с таким примером
Работает, с 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", напр массив вместо пары

Спасибо