Определение пересечения двух интервалов - есть ответ

ego-ist, 242 просмотра

Знаю, вопрос очень банальный, но сижу и жутко торможу. Есть контейнер, в нем лежат контейнеры, которые имеют два значения - начало интервала и конец интервала. Нужно перенести в новый контейнер только те контейнеры, множества которых пересекаются между собой. То есть, имея начальный контейнер cont = [[1,2], [1,3], [4,5], [6,8], [7,9]] нужно оставить [1,2], [1,3], [6,8], [7,9], а [4,5] убрать, помому что нет ниодного пересечея с этим интервалом. Заранее спасибо.

Ответы:

Удачник

Это тебе программно надо сделать? Я не знаю, как работать с контейнерами, потому что на этом языке не пишу, но для того, что ты хочешь алгоритм такой:
Цикл по всем интервалам i = 1 to n-1, где n - это количество интервалов.
Flag = 0
Внутренний цикл j = i+1 to n
Если (начало инт.(j) <= начало инт.(i) ) И (конец инт.(j) >= начало инт.(i), то Flag = 1
Если (начало инт.(j) >= начало инт.(i) ) И (начало инт.(j) <= конец инт.(i), то Flag = 1
Если (начало инт.(j) >= начало инт.(i) ) И (конец инт.(j) <= конец инт.(i), то Flag = 1
Если (начало инт.(j) <= начало инт.(i) ) И (конец инт.(j) >= конец инт.(i), то Flag = 1
Конец внутреннего цикла
Если Flag = 0, то инт. (i) выбрасывается.
Конец внешнего цикла.
// Но в таком случае никогда не выбрасывается последний интервал.
// Его надо проверить отдельно.
i = n
Flag = 0
Цикл j = 1 to n-1
Если (начало инт.(j) <= начало инт.(i) ) И (конец инт.(j) >= начало инт.(i), то Flag = 1
Если (начало инт.(j) >= начало инт.(i) ) И (начало инт.(j) <= конец инт.(i), то Flag = 1
Если (начало инт.(j) >= начало инт.(i) ) И (конец инт.(j) <= конец инт.(i), то Flag = 1
Если (начало инт.(j) <= начало инт.(i) ) И (конец инт.(j) >= конец инт.(i), то Flag = 1
Конец цикла
Если Flag = 0, то инт. (n) выбрасывается.
Конец.

11 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

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

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.