Алгоритм пересечения числовых интервалов. -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [216.73.216.60]

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray

Новое голосование

Алгоритм пересечения числовых интервалов.

rexx	Сообщ. #1 , 30.10.11, 11:51
Unregistered	Есть несколько числовых интервалов. Например, 1) 0-100 2) 40-50 3) 120-180 4) 200-300 5) 800-1000 6) 299-801 7) 1001-1100 ... Необходимо вычислить какие интервалы пересекаются. Какой наиболее оптимальный алгоритм?

MBo

Сообщ. #2 , 30.10.11, 12:15

Master

Профиль · PM

Поощрения: 3 Dgm

Рейтинг (т): 321

Отсортировать структуры вида (Координата, ЛевыйИлиПравыйКонец, IdИнтервала) по полю координаты
Затем проход по массиву. Встретили левый конец - добавили в список активных интервалов, встретили правый - удалили, выводя в результат пересечения с активными интервалами.

P.S. Если понадобятся еще какие-то действия, может быть лучше использовать структуру данных interval tree

Сообщение отредактировано: MBo - 30.10.11, 12:18

1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution time: 0,0171 ] [ 14 queries used ] [ Generated: 19.10.25, 20:27 GMT ]