Здравствуйте,
Имеется массив массивов отрезков, которые надо объеденить в один:
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]?