Смёржить отрезки

[Губанов Сергей Юрьевич]

На целочисленной (типа UInt64) прямой задан список отрезков {{начало1, конец1}, {начало2, конец2}, {начало3, конец3},...}. Отрезки могут соприкасаться, пересекаться и даже целиком поглощаться друг другом. Надо написать программу, которая быстро-быстро смёржит все пересечения/соприкосновения/поглощения и выдаст нормальный список отрезков (без пересечений/соприкосновений/поглощений).

Вопрос: как сделать это эффективно?

P. S.
Это списки диапазонов телефонных номеров. Всего номеров будет что-то около миллиона, списки конечно покороче. Не знаю точно, может быть 100 отрезков в списке, а может быть и 1000.

[Губанов Сергей Юрьевич]

На самом деле не требуется выдавать ответ именно в виде списка.

В ответе должна быть некая "нормальная" структура данных, не обязательно список отрезков.

Эта структура данных должна способствовать быстрому ответу на вопросы:
1) равна ли она другой такой же структуре данных или не равна;
2) попадает ли некий номер в какой либо из диапазонов или нет.

[ilovb]

Буквально на днях писал подобное:

Код: [Выделить]

// СписокПериодов: ТаблицаЗначений [Начало, Конец]
//
Функция СвернутьСписокПериодов(СписокПериодов)

Если СписокПериодов.Количество() > 1 Тогда

Набор = Новый Массив;

СписокПериодов.Сортировать("Начало");
ТекПериод = СписокПериодов[0];
Набор.Добавить(ТекПериод);

Для Каждого Период Из СписокПериодов Цикл

Если Период.Начало > ТекПериод.Конец Тогда
ТекПериод = Период;
Набор.Добавить(ТекПериод);
ИначеЕсли Период.Конец > ТекПериод.Конец Тогда
ТекПериод.Конец = Период.Конец;
КонецЕсли;

КонецЦикла;

ВОЗВРАТ СписокПериодов.Скопировать(Набор);

КонецЕсли;

ВОЗВРАТ СписокПериодов;

КонецФункции

[DIzer]

а что значит смержит? например..
{4,8} ,{1,12}, {3,6}, {4,8}- что она должна сделать?

[ilovb]

{1, 12}

[ilovb]

Если я правильно пониманию, то это разновидность задачи о покрытиях:
http://oberspace.dyndns.org/index.php/topic,307.0.html

[Peter Almazov]

На целочисленной (типа UInt64) прямой задан список отрезков {{начало1, конец1}, {начало2, конец2}, {начало3, конец3},...}. Отрезки могут соприкасаться, пересекаться и даже целиком поглощаться друг другом. Надо написать программу, которая быстро-быстро смёржит все пересечения/соприкосновения/поглощения и выдаст нормальный список отрезков (без пересечений/соприкосновений/поглощений).

Вопрос: как сделать это эффективно?

P. S.
Это списки диапазонов телефонных номеров. Всего номеров будет что-то около миллиона, списки конечно покороче. Не знаю точно, может быть 100 отрезков в списке, а может быть и 1000.

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

[DIzer]

не нужно искать, для этого достаточно обратиться с к элементу массива с индексом равным номеру... если  конечно нежирно иметь массив из 10^10 значений

[ilovb]

Ежели без сортировки, то вариант Peter Almazov самый ходовой.

albobin тут:
http://oberspace.dyndns.org/index.php/topic,307.0.html
так и делал

[ilovb]

Но такому способу нужно много памяти, раз там UInt64

add: DIzer уже упомянул этот момент

[DIzer]

Но такому способу нужно много памяти, раз там UInt64

add: DIzer уже упомянул этот момент

НЕТ. там uint64 это всего лишь НОМЕР элемента массива , сам элемент может быть всего лишь однобитным(истина, ложь...0,1)

[ilovb]

А... ну да... это ж додиез 

ps У меня в 1с нет такой возможности, потому не мыслю этими категориями 

[DIzer]

 один хрен массив большой- больше сотни мегабайт, да и заполнять его "в тупую" очень,ОЧЕНЬ накладно... тут надо смотреть более детально на задачу... например разбивать номер на первую тройку (код оператора) и все остальное...

[DIzer]

... так что , Ilovb,  не спешите выкидывать вариант с сортировками на помойку.. 

[Губанов Сергей Юрьевич]

Заполняй на прямой все точки из которых состоят отрезки.

Номер может быть из 18 десятичных цифр. 10^18 точек.