Обьединение множеств

[alexander.rsh]

Задача с беларусской областной олимпиады 2010.

Во входном файле имеются два множества, например:

[1, 3, 5..6]
[2, 6..8]

или

[]
[1000000]

Нужно их обьединить в одно, чтобы в выходном файле получилось:

в 1-ом случае:

[1..3, 5..8]

во втором:

[1000000]

может быть, у кого-то есть идеи, как это реализовать)
P.S. Длина каждой входной строки не превосходит 10000 символов, а каждый элемент множества не превосходит 10E9. Соответственно в выходном файле строка будет может превышать 10000 символов.

-- Пн мар 15, 2010 22:34:06 --

><>Sunny<><

[Cave]

Это не по математике задача.
А решается она сортировкой всех концов отрезков.

[malin]

вообще, это как раз таки математическая задача.(если я не прав, поправьте).

Скорее всего автор имел ввиду задачу об объединении неупорядоченных целочисленных множеств(т.е. вида $\{0, 23, 1, 99, 3, 4, 2\}$). Или , по-другому, неотсортированных массивов.

Задачу можно свести к построению минимального остовного леса. (алгоритмы Прима и Краскала).

Как вариант предлагаю рассмотреть граф, заданный списком рёбер. Рёбра получим следующим образом: если заданы два множества $\{a_1, a_2, ... a_n\}$ и $\{b_1, b_2, ..., b_k\}, k \ge n$, то рёбрами будут $\{(a_1,b_1),...,(a_n,b_n),(b_{n+1},b_{n+1}),...,(b_k,b_k))\}$

теперь каждому ребру приписываем вес 1 и применяем любой из алгоритмов построения минимального остовного леса.

можно при этом последние $k-n$ рёбер сразу включить в остовный лес и не возиться с ними

P.S.: Какая-то очень похожая задача встречается при изучении бинарных деревьев поиска. Наверное, объединение деревьев. В общем, что-то там про графы