Проверка на пересечение линейных интервалов времени

27.03.2014 13:22
13

Очень часто при работе с интервалами времени встает проблема определения их пересечения. Так как же максимально просто и правильно это определить?

На самом деле все не так уж сложно.

Пусть будут даны два интервала a и b, у которых соответственно задано начало и конец: a.start / a.end и b.start / b.end и считаем, что интервалы заданы от некого начала до некого конца, включая этот конец.

Самое простое - это написать условие для не пересекающихся интервалов.

Непересечение, это когда начало одного интервала больше конца другого интервала, или конец одного интервала меньше начала другого:
a.start > b.end OR a.end < b.start

Соответственно, пересечение - это отрицание того, что мы получили - т.е. если для интервалов выполняется NOT( a.start > b.end OR a.end < b.start )

Теперь раскрываем по правилам логики скобки и получаем a.start <= b.end AND a.end >= b.start

Не смотря на сложность понимания работы этой формулы - поверьте - она Вам даст все пересекающиеся интервалы.
Данная формула считает, что start и end входят в интервал, т.е. например интервалы [0, 5] и [5, 10] будут пересекаться.

Если нужна формула, в которой end не входит в интервал, то она будет следующего вида: a.start < b.end AND a.end > b.start

27.03.2014, Protocoder
Ищущий_решение13.02.2015 21:11:05#ответить
a{1, 8} b{3, 5}
a.start < b.end AND a.end > b.start
1 5 8 3
иии
у меня 1 интервал находится в другом, это как раз случай пересечения.
так что - ошибка.
Protocoder14.02.2015 02:32:11#ответить
А что Вас смущает?

В Вашем же примере: 1<5 и 8>3 => (1 меньше 5?)=да И (8 больше 3?)=да

Ну т.е. да, пересекаются, что, собственно говоря, так и есть, поскольку интервал b лежит внутри интервала a. Все верно, никаких ошибок.
Алексей29.04.2015 17:13:15#ответить
Спасибо, всё отлично работает если вникнуть в суть! )
Вадим12.08.2015 21:48:32#ответить
Когда выводились условия пересечения, Вы использовали (>=) и (<=), почему в конечном результате получились (<) и (>) ? К примеру, интервалы [0, 1] и [1, 2] пересекаются, но по Вашим условиям - нет.
Protocoder12.08.2015 23:00:57#ответить
При логическом инвертировании, знак < или > меняется на противоположный и равно - поэтому так.

По поводу интервалов - тут вопрос в граничных условиях.
Я считал, что интервал задается от некого начала до некого конца, но не включая этот конец, а Вы считаете, что конец включен в интервал.

Согласен, что Ваш вариант более общий, по этому дополнил статью и изменил формулу.

А Вам огромное спасибо за внимательность и что нашли время написать.
Андрей04.05.2017 18:05:33#ответить
"Их" вариант, может быть, и более общий, но только со временем работает некорректно.

Т.к. при указании, например, 00:00-00:05, конечное значение не включается в интервал, т.е. событие оканчивается при наступлении 5-ой минуты, а не по её истечении.

Поэтому интервал 00:05-00:10 НЕ пересекается с первым, а по "более общему" варианту - пересекается.

Заголовок вашего поста звучит как "пересечение линейных интервалов времени", поэтому формула должна работать со временем, а не с "более общими" вариантом. Откатите, плиз, изменения - ваш вариант изначально был корректным.
Protocoder06.05.2017 11:57:48#ответить
Добавил в статью.
Павел27.02.2017 16:56:10#ответить
Супер! Целый день пытался написать условия на пересечение двух отрезков...
Получалась куча условий на частные случаи (один внутри другого) + на начало и конец первого на вхождение во второй......
А тут буквально 2 условия с AND -- и готово!!!
:)) Спасибо огромное!!!
Protocoder27.02.2017 22:43:33#ответить
Рад, что пригодилось :)
Вячеслав09.04.2017 13:29:14#ответить
Благодарю! Вместо формальных 4 проверок всего одна. Изящно.
Гость10.08.2017 00:57:03#ответить
Весь вечер бился, спасибо за формулу, очень помогло

Если вдруг кому-нибудь понадобится, я решал задачу входит ли указанный промежуток в ночь (21:00 до 06:00 утра). Разбейте ночь на две части 21:00-23:59 и 00:00-06:00 и сравните нужный вам промежуток с двумя интервалами.
Владимир18.04.2018 21:29:53#ответить
Признак пересечения
( start1 - end2 ) * ( start2 - end1 ) > 0
Protocoder22.04.2018 01:57:45#ответить
Спасибо - да, есть и такой вариант - но тот что в статье - куда более простой.
Причем как с точки зрения производительности, так и с точки зрения понимания.

Единственный плюс этой формулы (емнип) - "end" может быть больше "start" - т.е. они могут быть не приведены к правильному порядку.
Написать комментарий