Здравствуйте,
Имеется массив массивов отрезков, которые надо объеденить в один:
arr[seg1,seg2,seg3,....];
seg1=[{x11,x12},{x13,x14},{x15,x16},...], seg2=[{x21,x22},{x23,x24},{x25,x26},...],...
x1<x2<x3<.., 0<x<1,000,000,
самое приблизительное колличество в seg x= от 2 до ~10<, колличество в arr seg= от 100 до ~1000
а на выходе должно быть:
seg1=[{x1,x2},{x3,x4},{x5,x6},...]

Напр. если на входе: arr[{{1,4},{43,99},{150,200}},{{2,3},{55,105}}]
на выходе будет: {{1,4},{43,105},{150,200}}

Самый не оптимальный и быстрый вар. который напрашивается — это пройтись по каждой ноде в кажом seg[2..n] в arr и объединять их с нодами seg1, при каждом объединение проходя по каждой ноде из seg1, т.е. за время O(n).
Но, возномжно можно как-то быстрее искать ноды в seg1 с которыми надо объеденять ноды из seg[2..n]?

Здравствуйте, #John, Вы писали:

J>Имеется массив массивов отрезков, которые надо объеденить в один:
J>arr[seg1,seg2,seg3,....];
J>seg1=[{x11,x12},{x13,x14},{x15,x16},...], seg2=[{x21,x22},{x23,x24},{x25,x26},...],...
J>x1<x2<x3<.., 0<x<1,000,000,
...
J>Самый не оптимальный и быстрый вар. который напрашивается — это пройтись по каждой ноде в кажом seg[2..n] в arr и объединять их с нодами seg1, при каждом объединение проходя по каждой ноде из seg1, т.е. за время O(n).
J>Но, возномжно можно как-то быстрее искать ноды в seg1 с которыми надо объеденять ноды из seg[2..n]?

Я правильно понял, что внутри всех массивов отрезки упорядочены?
Тогда сортировка слиянием, точнее, её этап "Соединение двух упорядоченных массивов в один".

Здравствуйте, #John, Вы писали:

J>Самый не оптимальный и быстрый вар. который напрашивается — это пройтись по каждой ноде в кажом seg[2..n] в arr и объединять их с нодами seg1, при каждом объединение проходя по каждой ноде из seg1, т.е. за время O(n).
Ну да, merge sort получается. O(n), если отрезки предварительно отсортированы, O(nlog(n)) — если нет.

Добрый вечер!
Можно воспользоваться тем, что после объединения 2-х массивов len(seg1) = n1 и len(seg2) = n2 с большой вероятностью получится массив с меньшей длиной чем n1+n2 , из-за пересечения отрезков. Объединять не сразу все массивы, а третий с результатом объединения первых двух.
И в сортировке слиянием следующий элемент можно искать не инкрементом, а поиском [забыл название]: просматриваются 1, 2, 4, 8... элементы; если искомый элемент находится между 2ⁱ и 2ⁱ⁺¹, то ищем бинарным поиском между ними. Это позволит в таких случаях: arr[{{1,100}},{{1,2},{2,3}, ..., {99,100}}] сливать массивы не за O(n), а за O(log n), при этом не сильно ухудшая время сливания массивов с равномерным распределением отрезков.
И первый и второй вариант зависит от реального распределения отрезков, так что надо тестить.