Russian Qt Forum
Март 29, 2024, 02:21 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: Слияние диапазонов  (Прочитано 3546 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


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

Спасибо
Записан
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #1 : Январь 25, 2022, 16:21 »

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

Сообщений: 574


Просмотр профиля
« Ответ #2 : Январь 25, 2022, 23:31 »

Используйте для поиска в упорядоченном векторе функции алгоритмов https://en.cppreference.com/w/cpp/algorithm/equal_range, а далее решайте, что следует сделать - изменить значение по одному из итераторов или вставить значение в контейнер.
« Последнее редактирование: Январь 25, 2022, 23:33 от ssoft » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #3 : Январь 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, а далее решайте, что следует сделать - изменить значение по одному из итераторов или вставить значение в контейнер.
Наверно Вы имели ввиду получить диапазон всех пар пересекающих вставляемую. Это особо ничего не экономит, а проверяет все эл-ты (в отличие от 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 } }

Ой! Совсем забыл - есть же еще ИИ!!!  Улыбающийся
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3257


Просмотр профиля
« Ответ #4 : Январь 26, 2022, 10:55 »

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

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

да, оч сложно, задачка уровня medium
Записан
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #5 : Январь 26, 2022, 11:25 »

Зачем тупой пробег если есть хотя бы lower_bound?
А он как то по другому в векторе найдет?
Записан
Old
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4349



Просмотр профиля
« Ответ #6 : Январь 26, 2022, 11:28 »

А он как то по другому в векторе найдет?
Вектор отсортирован же. Конечно найдет по другому. Улыбающийся
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #7 : Январь 27, 2022, 08:37 »

да, оч сложно, задачка уровня medium
Не понял, а писать бум или уже готовое нашли?  Непонимающий
Записан
Авварон
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 3257


Просмотр профиля
« Ответ #8 : Январь 27, 2022, 17:23 »

да, оч сложно, задачка уровня medium
Не понял, а писать бум или уже готовое нашли?  Непонимающий

я уже писал, хз
Записан
ssoft
Программист
*****
Offline Offline

Сообщений: 574


Просмотр профиля
« Ответ #9 : Январь 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{} );
}
 
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #10 : Январь 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", напр массив вместо пары

Спасибо
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.126 секунд. Запросов: 23.