Объединение диапазонов/отрезков

[Igors]

Добрый день

Есть QVector<int> хранящий "отрезки" или "диапазоны", напр номера страниц. Пример

{ 1, 10, 15, 20 };  // страницы с 1 по 10 включительно и с 15 по 20

Вектор всегда сортирован и имеет четное числр эл-тов. Требуется пополнять этот вектор новыми отрезками, при этом сливая их если необходимо. Примеры

{ 1, 10, 15, 20 } + { 25, 30 } = { 1, 10, 15, 20, 25. 30 } 
{ 1, 10, 15, 20 } + { 21, 30 } = { 1, 10, 15, 30 } 

Может в std есть что-нибудь "эдакое"? Или это и так легко написать (тогда покажите как, у меня получается как-то не очень легко)

Спасибо

[qate]

https://stackoverflow.com/questions/4748184/how-to-efficiently-merge-int-ranges-in-a-stream
не ?

[Igors]

Не, но тут есть название "interval tree". Выходим на boost::interval_map, вроде "оно", но, как всегда, задрочено 
Ладно, обойдусь великом, может в след раз. Спасибо за наводку

[sergek]

Мне кажется, если вектора разделить на отдельные отрезки ({ 1, 10, 15, 20 } -> { 1, 10}, {15, 20 }), отсортировать, то задача будет решаться значительно легче. Если уже не решена. А потом все слить в кучу.

[Igors]

Мне кажется, если вектора разделить на отдельные отрезки ({ 1, 10, 15, 20 } -> { 1, 10}, {15, 20 }), отсортировать, то задача будет решаться значительно легче.

Не уловил идею, за счет чего легче? По-моему все равно возня с lower_bound  (контейнер всегда сортирован)

Если уже не решена.

Конечно решена, но это час-другой довольно кропотливой работы, да и нет уверенности что где-то не насвистел. Поэтому "попастись" конечно хотелось бы.   

[Racheengel]

Ну есть примитивное решение, основанное на двоичной карте (собственно принцип z-буфера).
Все диапазоны разворачиваются в 1-мерное двоичное пространство (от 0 до max), каждое имеющееся значение помечается как 1, иначе 0. Затем повторяем для другого вектора и т.д. В конце делаем обратную операцию - все подряд установленные биты конвертируем в диапазоны.
Будет работать, естественно, только для целых чисел и когда max заранее известен.

[deMax]

Закидываем в отсортированный список первый диапазон, который хранит время и бит(1=начало или 0=конец диапазона). Потом в этот список добавляем аналогично второй диапазон(список уже отсортирован).
А потом из списка считываем в ответ,

Код:

int deep = 0;
for(const auto &item: items) {
  if(item.bit) { // начало диапазона
    if(deep++) anser << item.time; } // тут лучше уйти от постинкримента(if(deep)...;++deep;), просто так нагляднее
  else // конец диапазона
    if(--deep) answer << item.time; }
}

а потом пройтись по списку и удалить пары одинаковых чисел. (в цикле наверное сложнее будет)

[Igors]

Ну есть примитивное решение, основанное на двоичной карте (собственно принцип z-буфера).
Все диапазоны разворачиваются в ...

Ну все-таки примитивизм имеет какие-то (разумные) границы 

Закидываем в отсортированный список первый диапазон, который хранит время и бит(1=начало или 0=конец диапазона). Потом в этот список добавляем аналогично второй диапазон(список уже отсортирован).
А потом из списка считываем в ответ,

Код:

int deep = 0;
for(const auto &item: items) {
  if(item.bit) { // начало диапазона
    if(deep++) anser << item.time; } // тут лучше уйти от постинкримента(if(deep)...;++deep;), просто так нагляднее
  else // конец диапазона
    if(--deep) answer << item.time; }
}

а потом пройтись по списку и удалить пары одинаковых чисел. (в цикле наверное сложнее будет)

Совершенно не понял этот набросок. Как это будет работать для примеров стартового поста?

[deMax]

Igors
первый диапазон 1-6, второй 3-4, 5-7. слили в один список сохранив флаги (o-open, c-close) 1o 3o 4c 5o 6c 7c. глубина вначале - (0) открывая диапазон глубина увеличивается и наоборот, тогда (0) 1o (1) 3o (2) 4c (1) 5o (2) 6c (1) 7c (0) в диапазон попадают только переходы 0->1 и 1->0. итого 1 7

[Igors]

первый диапазон 1-6, второй 3-4, 5-7. слили в один список сохранив флаги (o-open, c-close) 1o 3o 4c 5o 6c 7c. глубина вначале - (0) открывая диапазон глубина увеличивается и наоборот, тогда (0) 1o (1) 3o (2) 4c (1) 5o (2) 6c (1) 7c (0) в диапазон попадают только переходы 0->1 и 1->0. итого 1 7

Теперь понял, спасибо. Вполне рабочий вариант, но может оказаться громоздким/неуклюжим т.к. надо сливать контейнеры а потом удалять. Для "массового" слияния это оправдано, но если добавляется 1-2 (как в стартовом посте) то нет.

[deMax]

Можно без дополнительного диапазона. Хранить 2 числа(текущее и предыдущее значение) и бит четности(для каждого диапазона, чтобы знать начало это или конец) из первого диапазона и из второго. Увеличивать итератор для диапазона с меньшим числом. Смысл тот же, просто копирования в отдельный диапазон нет.