Проверка на пересечение линейных интервалов времени
27.03.2014 13:22
24
Очень часто при работе с интервалами времени встает проблема определения их пересечения. Так как же максимально просто и правильно это определить?
На самом деле все не так уж сложно.
Пусть будут даны два интервала 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
a.start < b.end AND a.end > b.start
1 5 8 3
иии
у меня 1 интервал находится в другом, это как раз случай пересечения.
так что - ошибка.
В Вашем же примере: 1<5 и 8>3 => (1 меньше 5?)=да И (8 больше 3?)=да
Ну т.е. да, пересекаются, что, собственно говоря, так и есть, поскольку интервал b лежит внутри интервала a. Все верно, никаких ошибок.
По поводу интервалов - тут вопрос в граничных условиях.
Я считал, что интервал задается от некого начала до некого конца, но не включая этот конец, а Вы считаете, что конец включен в интервал.
Согласен, что Ваш вариант более общий, по этому дополнил статью и изменил формулу.
А Вам огромное спасибо за внимательность и что нашли время написать.
Т.к. при указании, например, 00:00-00:05, конечное значение не включается в интервал, т.е. событие оканчивается при наступлении 5-ой минуты, а не по её истечении.
Поэтому интервал 00:05-00:10 НЕ пересекается с первым, а по "более общему" варианту - пересекается.
Заголовок вашего поста звучит как "пересечение линейных интервалов времени", поэтому формула должна работать со временем, а не с "более общими" вариантом. Откатите, плиз, изменения - ваш вариант изначально был корректным.
Получалась куча условий на частные случаи (один внутри другого) + на начало и конец первого на вхождение во второй......
А тут буквально 2 условия с AND -- и готово!!!
:)) Спасибо огромное!!!
Если вдруг кому-нибудь понадобится, я решал задачу входит ли указанный промежуток в ночь (21:00 до 06:00 утра). Разбейте ночь на две части 21:00-23:59 и 00:00-06:00 и сравните нужный вам промежуток с двумя интервалами.
( start1 - end2 ) * ( start2 - end1 ) > 0
Причем как с точки зрения производительности, так и с точки зрения понимания.
Единственный плюс этой формулы (емнип) - "end" может быть больше "start" - т.е. они могут быть не приведены к правильному порядку.
Длинна пересекающегося отрезка может быть вычислена следующим образом MAX(-MAX(a.min,b.min)+MIN (a.max,b.max),0)
Т.е. например не-пересечение с интервалом, заданным только правой границей - это проверка что левая граница проверяемого интервала (начало) > правой границы, конец интервала для этого случая нет смысла проверять.