Проверка, перекрываются ли два «временных диапазона» друг с другом

Question

У меня есть объект, сохраненный в дБ с диапазоном времени (t1): 11:45-00:15. Теперь у меня есть другой временной диапазон от запроса: (t2) 00:05-00:10. Какой самый оптимальный способ определить, перекрывает ли этот новый временной диапазон t2 уже сохраненный объект с временными диапазонами t1. Это случай полуночи, когда день меняется. За тот же день я успешно смог найти перекрывающиеся временные диапазоны. У меня нет поля datetime, скорее у меня есть только поле time, поэтому я должен обойтись тем, что у меня уже есть.

В моделях t1 будет храниться как:

start_time = TimeField(null=True, blank=True, db_index=True)
end_time = TimeField(null=True, blank=True, db_index=True)

, поэтому 11:45 будет сохранено в start_time, а 00:15 будет сохранено в end_time

Answer 1

Я предполагаю, что в случаях, когда start_time больше, чем end_time, временной диапазон должен просто перекрываться, так как время было циклическим, и нам просто наплевать на дату (другими словами, эти диапазоны представляют события которые происходят каждый день, и мы хотим определить, перекрывается ли какое-либо событие с каким-либо другим событием)

С этим предположением, вот быстрый ответ:

if t2.start_time > t2.end_time:
    condition = (
        Q(start_time__gt=F('end_time')) |
        Q(start_time__lt=t2.end_time) |
        Q(end_time__gt=t2.start_time)
    )
else:
    condition = (
        Q(start_time__gt=F('end_time'), start_time__lt=t2.end_time) |
        Q(start_time__gt=F('end_time'), end_time__gt=t2.start_time) |
        Q(start_time__lt=t2.end_time, end_time__gt=t2.start_time)
    )

Объяснение

Существует 24 случая организации времени начала и окончания каждого события (исключая случаи, когда любые две даты равны). Из этих 24 случаев 20 из них означают, что есть совпадение, а 4 из них означают, что нет совпадения. Поскольку в перекрытии нет гораздо меньшего количества случаев, давайте рассмотрим его более подробно, поэтому вот эти 4 случая:

1. t1.end_time < t2.start_time < t2.end_time < t1.start_time
2. t1.start_time < t1.end_time < t2.start_time < t2.end_time
3. t2.start_time < t2.end_time < t1.start_time < t1.end_time
4. t2.end_time < t1.start_time < t1.end_time < t2.start_time

Вы можете представить эти случаи в коде Python следующим образом (добавлены лишние пробелы, чтобы показать, как мы можем их сгруппировать):

(                                t1.start_time > t2.end_time and t2.start_time > t1.end_time and t2.start_time < t2.end_time) or \ # 1.
(t1.start_time < t1.end_time                                 and t2.start_time > t1.end_time and t2.start_time < t2.end_time) or \ # 2.
(t1.start_time < t1.end_time and t1.start_time > t2.end_time                                 and t2.start_time < t2.end_time) or \ # 3.
(t1.start_time < t1.end_time and t1.start_time > t2.end_time and t2.start_time > t1.end_time                                )      # 4. 

Как мы видим, можно сказать, что элементы не пересекаются, если применимо какое-либо 3 из этих 4 условий:

(
    t1.start_time < t1.end_time,
    t1.start_time > t2.end_time,
    t2.start_time > t1.end_time,
    t2.start_time < t2.end_time,
)

Если мы хотим выяснить, перекрываются ли 2 элемента, мы должны отменить это условие. Таким образом, элементы перекрываются, если выполняется любое из 2 из этих 4 условий:

(
    t1.start_time > t1.end_time,
    t1.start_time < t2.end_time,
    t2.start_time < t1.end_time,
    t2.start_time > t2.end_time,
)

полное состояние выглядит так:

t1.start_time > t1.end_time and t1.start_time < t2.end_time or \
t1.start_time > t1.end_time and t2.start_time < t1.end_time or \
t1.start_time > t1.end_time and t2.start_time > t2.end_time or \
t1.start_time < t2.end_time and t2.start_time < t1.end_time or \
t1.start_time < t2.end_time and t2.start_time > t2.end_time or \
t2.start_time < t1.end_time and t2.start_time > t2.end_time

Одеваем его в набор запросов django, так как у нас есть 1 условие, которое мы можем проверить перед его выполнением (мы можем проверить, если start_time из t2 меньше end_time из t2), мы можем разделить его на 2 случая и упростить их оба.

if t2.start_time > t2.end_time:
    condition = (
        Q(start_time__gt=F('end_time')) |
        Q(start_time__lt=t2.end_time) |
        Q(end_time__gt=t2.start_time)
    )
else:
    condition = (
        Q(start_time__gt=F('end_time'), start_time__lt=t2.end_time) |
        Q(start_time__gt=F('end_time'), end_time__gt=t2.start_time) |
        Q(start_time__lt=t2.end_time, end_time__gt=t2.start_time)
    )

А как насчет равных?

Да ... Мы пропустили это ... Нам нужно принять 3 решения, чтобы включить их.

1. Может ли любой диапазон иметь длину 0 (начало и конец равны) и не сталкиваться ни с чем?
2. Может ли любой диапазон иметь длину 24 часа (начало и конец равны) и сталкиваться со всем?
3. Если начало одного диапазона равно концу другого диапазона, перекрываются ли они?

1-е и второе условие не могут быть оба да. Если вы ответили на все эти вопросы «нет», то все готово, код, показанный выше, будет работать в вашем случае. Если вы ответили «да» на любой вопрос, примените соответствующую модификацию из списка ниже:

1. Добавьте .exclude(start_time=F('end_time')) к окончательному набору запросов и предположите, что t2 не перекрывается с чем-либо еще, если t2.start_time == t2.end_time, и просто пропустите проверку
2. Добавьте | Q(start_time=F('end_time') к обоим условиям и предположите, что t2 перекрывается со всем остальным, если t2.start_time == t2.end_time, и просто пропустите проверку
3. Замените каждые __gt на __gte и каждые __lt на __lte в обоих условиях, когда вместо правой стороны F имеется t2.