Пересечение N отрезков на числовой прямой

@Alphyx · Регистрация: 13.08.2017

Студворк — интернет-сервис помощи студентам

Даны N отрезков на числовой прямой с их правой и левой координатой (L_x и R_x) в произвольном порядке. Нужно узнать, есть ли для i-ого отрезка такой j-ый, который пересекается с ним, то есть выполняются условия: L_j>L_i, L_j<R_i, R_j>R_i. Случаи, когда отрезок полностью входит в другой (L_j<=L_i, R_j>=R_i) или имеет только одну общую точку (L_i = L_j или R_i = R_j) рассматривать не нужно.
Есть ли эффективный алгоритм, который найдёт такие отрезки меньше чем за O(n²)? Перебором ясно как находить, но нужно что-то более быстрое.

@vantfiles · 28.02.2020, 16:38

Может быть отсортировать для начала по левой координате? Тогда проверки становятся достаточно простыми...

@Alphyx · 28.02.2020, 17:02 **[ТС]**

Да, я уже отсортировал в одном массиве по левой, в другом по правой. Только не понимаю, как можно найти среди этого пересечения, ведь нужно одновременно проверять обе координаты.

Добавлено через 9 минут
То есть, отсортировав по левой координате, можно точно знать, что последующие L всегда больше или равны L_i. Далее нужно перебирать в цикле отрезки j пока истинно условие R_i < L_j. Когда L_j становится больше, то нет смысла проверять. Но из-за перебора сложность алгоритма будет близка к O(n²), если я верно понимаю.

@vantfiles · 28.02.2020, 18:18

Сообщение от Alphyx

Нужно узнать, есть ли для i-ого отрезка такой j-ый

Вам нужно проверить один отрезок на пересечение или все? Вы правильно сформулировали задачу?

@Alphyx · 28.02.2020, 22:05 **[ТС]**

Нужно проверить все N отрезков. В цикле перебираются i-ые отрезки, и необходимо найти, с какими есть пересечение.

Добавлено через 2 часа 11 минут
Возможно ли это сделать менее чем за O(n²) операций?

@vantfiles · 28.02.2020, 23:00

Не по теме:

Ну тут подумать надо (с)

@Serg_o_Grey · 28.02.2020, 23:18

Справочник по высшей математике Выгодского. параграф 19 - Пересечение прямых

@vantfiles · 28.02.2020, 23:46

Не по теме:

Сообщение от Serg_o_Grey

Справочник по высшей математике Выгодского. параграф 19 - Пересечение прямых

Слышал, где звон, да не слышал, где он...

@Serg_o_Grey · 29.02.2020, 18:03

vantfiles, поговорка не так звучит, но да, все верно

Alphyx, После проверки одного отрезка на пересечение с другим просто исключите эту пару из проверок для последующих итераций
На последней итерации нужно бутет проверить всего два отрезка
И вот у вас уже есть алгоритм который выполнит задачу за O(n²/2)

@vantfiles · 29.02.2020, 18:29

Сообщение от Serg_o_Grey

просто исключите эту пару

Один отрезок могут пересекать несколько. Так что исключать не годится.

@Serg_o_Grey · 29.02.2020, 18:38

vantfiles, не уверен что Вы до конца осознали что именно нужно исключать. Может быть мне нужно было детальней расписать
исключить сочетание одного отрезка с другим, а не сами отрезки

отрезки: 1, 2, 3, 4
проверки:
1. {1,2},{1,3},{1,4}
2. {2,3},{2,4}
3. {3,4}

@vantfiles · 29.02.2020, 18:38

Сообщение от Serg_o_Grey

не уверен что Вы до конца осознали что именно нужно исключать.

Я тоже.

Сообщение от Serg_o_Grey

После проверки одного отрезка на пересечение с другим просто исключите эту пару из проверок для последующих итераций

Поясните эту фразу, пожалуйста.

@Serg_o_Grey · 29.02.2020, 18:40

пояснил выше уже

@vantfiles · 29.02.2020, 18:42

Вы просто последовательно идете по отрезкам - это и есть перебор вариантов.

@Serg_o_Grey · 29.02.2020, 18:43

да, но это не O(n²)

это то чего хотел заказчик

@vantfiles · 29.02.2020, 18:54

Вы предложили сперва одно, потом после критики предложили совсем другое - и сейчас утверждаете, что это одно и то же.
Кстати, это и не O(n²/2) -- вы привели пример для 4 элементов с шестью итерациями... Как-то не складывается...

@Serg_o_Grey · 29.02.2020, 20:14

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

специально для vantfiles
под итерациями имел в виду один проход цикла. Виноват (
ну и
{1,2},{1,3},{1,4},{1,5},{1,6}
{2,3},{2,4},{2,5},{2,6}
{3,4},{3,5},{3,6}
{4,5},{4,6}
{5,6}

Такие задачи решаются только перебором. Самый действенный способ оптимизации - уменьшить количество вариантов перебора.
когда заказчик написал что ему ясно как находить перебором, он явно заблуждался. Не учел что полный перебор производить не обязательно

vantfiles, Вы же ищите принципиально иное, отличающееся от перебора решение
некоторые оптимизации в сочетании с очевидным исключением вариантов еще возможны, но это уже тонкости

Добавлено через 32 минуты
vantfiles, С определением сложности алгоритма я до сих пор не удосуживался ознакомиться. Но теперь это полностью меняет дело. Прекращаю свои ничтожные инсинуации.

@eaa · 01.03.2020, 10:52

заметающая(сканирующая) прямая. не?

@Shamil1 · 01.03.2020, 12:13

Сообщение от Alphyx

Есть ли эффективный алгоритм, который найдёт такие отрезки меньше чем за O(n2)?

Нужно найти список. Максимальная длина списка O(n2)? Если так, то нет.

@vantfiles · 01.03.2020, 15:13

Serg_o_Grey, кажется правы как раз Вы.

Достаточно посмотреть на рисунок.
Зеленая область симметрична красной - достаточно обойти с проверками одну из них.
Отсюда количество итераций равно ( N² - N ) / 2

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@Alphyx 0 / 0 / 0 Регистрация: 13.08.2017 Сообщений: 11

	Пересечение N отрезков на числовой прямой 28.02.2020, 16:06. Показов 8945. Ответов 19 Метки алгоритм, отрезки (Все метки) Даны N отрезков на числовой прямой с их правой и левой координатой (L_x и R_x) в произвольном порядке. Нужно узнать, есть ли для i-ого отрезка такой j-ый, который пересекается с ним, то есть выполняются условия: L_j>L_i, L_j<R_i, R_j>R_i. Случаи, когда отрезок полностью входит в другой (L_j<=L_i, R_j>=R_i) или имеет только одну общую точку (L_i = L_j или R_i = R_j) рассматривать не нужно. Есть ли эффективный алгоритм, который найдёт такие отрезки меньше чем за O(n²)? Перебором ясно как находить, но нужно что-то более быстрое. 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	28.02.2020, 16:38
	Может быть отсортировать для начала по левой координате? Тогда проверки становятся достаточно простыми... 0

@Alphyx 0 / 0 / 0 Регистрация: 13.08.2017 Сообщений: 11
	28.02.2020, 17:02 [ТС]
	Да, я уже отсортировал в одном массиве по левой, в другом по правой. Только не понимаю, как можно найти среди этого пересечения, ведь нужно одновременно проверять обе координаты. Добавлено через 9 минут То есть, отсортировав по левой координате, можно точно знать, что последующие L всегда больше или равны L_i. Далее нужно перебирать в цикле отрезки j пока истинно условие R_i < L_j. Когда L_j становится больше, то нет смысла проверять. Но из-за перебора сложность алгоритма будет близка к O(n²), если я верно понимаю. 0

@Alphyx 0 / 0 / 0 Регистрация: 13.08.2017 Сообщений: 11
	28.02.2020, 22:05 [ТС]
	Нужно проверить все N отрезков. В цикле перебираются i-ые отрезки, и необходимо найти, с какими есть пересечение. Добавлено через 2 часа 11 минут Возможно ли это сделать менее чем за O(n²) операций? 0

@vantfiles
	28.02.2020, 23:00
	Не по теме: Ну тут подумать надо (с) 0

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	28.02.2020, 23:18
	Справочник по высшей математике Выгодского. параграф 19 - Пересечение прямых 0

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	29.02.2020, 18:03
	vantfiles, поговорка не так звучит, но да, все верно Alphyx, После проверки одного отрезка на пересечение с другим просто исключите эту пару из проверок для последующих итераций На последней итерации нужно бутет проверить всего два отрезка И вот у вас уже есть алгоритм который выполнит задачу за O(n²/2) 0

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	29.02.2020, 18:38
	vantfiles, не уверен что Вы до конца осознали что именно нужно исключать. Может быть мне нужно было детальней расписать исключить сочетание одного отрезка с другим, а не сами отрезки отрезки: 1, 2, 3, 4 проверки: 1. {1,2},{1,3},{1,4} 2. {2,3},{2,4} 3. {3,4} 0

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	29.02.2020, 18:40
	пояснил выше уже 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	29.02.2020, 18:42
	Вы просто последовательно идете по отрезкам - это и есть перебор вариантов. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	01.03.2020, 10:52
	заметающая(сканирующая) прямая. не? 0

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	29.02.2020, 18:43
	да, но это не O(n²) это то чего хотел заказчик 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	29.02.2020, 18:54
	Вы предложили сперва одно, потом после критики предложили совсем другое - и сейчас утверждаете, что это одно и то же. Кстати, это и не O(n²/2) -- вы привели пример для 4 элементов с шестью итерациями... Как-то не складывается... 0

@Serg_o_Grey 116 / 106 / 51 Регистрация: 29.03.2016 Сообщений: 480
	29.02.2020, 20:14
	Мне кажется что, когда предложил учебник по высшей математике, я признал свою неправоту . Там я дейстительно не стал вчитываться в вопрос специально для vantfiles под итерациями имел в виду один проход цикла. Виноват ( ну и {1,2},{1,3},{1,4},{1,5},{1,6} {2,3},{2,4},{2,5},{2,6} {3,4},{3,5},{3,6} {4,5},{4,6} {5,6} Такие задачи решаются только перебором. Самый действенный способ оптимизации - уменьшить количество вариантов перебора. когда заказчик написал что ему ясно как находить перебором, он явно заблуждался. Не учел что полный перебор производить не обязательно vantfiles, Вы же ищите принципиально иное, отличающееся от перебора решение некоторые оптимизации в сочетании с очевидным исключением вариантов еще возможны, но это уже тонкости Добавлено через 32 минуты vantfiles, С определением сложности алгоритма я до сих пор не удосуживался ознакомиться. Но теперь это полностью меняет дело. Прекращаю свои ничтожные инсинуации. 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	01.03.2020, 15:13
	Serg_o_Grey, кажется правы как раз Вы. Достаточно посмотреть на рисунок. Зеленая область симметрична красной - достаточно обойти с проверками одну из них. Отсюда количество итераций равно ( N² - N ) / 2 Миниатюры 0