Пересечение 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

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

	Пересечение N отрезков на числовой прямой 28.02.2020, 16:06. Показов 8854. Ответов 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