Проверка перекрытия нового интервала — MySQL (или PHP)

Question

Проверка перекрытия нового интервала — MySQL (или PHP)

Я думал о том, как я могу упростить проблему, представленную здесь. Сложный MySQL Query — Проверка перекрывающихся интервалов DATE

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

Schedules
schedule_id     |     start     |       end
1               |       1       |       3
2               |       4       |       7
3               |       8       |       13
4               |      15       |       16
5               |      18       |       24
6               |      25       |       28

Я пытаюсь вставить новый интервал так, чтобы [a, b] не перекрывался ни с каким другим интервалом. Соображения:

Да, я могу вытащить всю таблицу в массив и выполнить O (N) поиск по ней. Это скучно.
Я предпочитаю делать это в MySQL, поэтому мне не нужно каждый раз разбирать таблицу, которая может быть сколь угодно большой.

Смотрите следующее изображение. Это представляет границы того, что можно, а что нельзя вставлять. http://i.stack.imgur.com/jE59w.png

4

intervals mysql php scheduling

Решение

Другие решения

Вы можете сформулировать вставку как:

insert into schedules(start, end)
select s, e
from (select $start s, $end as e) t
where not exists (select 1
from schedules s2
where s.start <= t.end and s.end >= t.start
);

Это будет только вставить значение, если оно не перекрывается с существующей строкой в таблице.

0

Источник

Accepted Answer

Использование следующих сокращений:

[Старый] : = существующий диапазон
[Новый] : = вставить диапазон
Операционные системы : = (старый) существующий_ран.старт
О.Е. : = (старый) существующий_рандж. конец
NS : = (новый) insertting_range.start
Небраска : = (новый) insertting_range.end

условие перекрытия двух диапазонов (старого и нового): (OS < NE) AND (OE > NS)

Хотя решение может быть не тривиальным, его не так сложно найти:

Нет наложения, если новый диапазон полностью до или после существующего диапазона: [new] <= [old] OR [old] <= [new] и это означает, что:

(NE <= OS) OR (OE <= NS)

Обсуждая это утверждение, мы получаем условие перекрытия:

!( (NE <= OS) OR (OE <= NS) )

Сейчас использую Закон де Моргана мы можем написать это как

!(NE <= OS) AND !(OE <= NS)

И это эквивалентно

(NE > OS) AND (OE > NS)

который можно переписать как

(OS < NE) AND (OE > NS)

Теперь мы можем найти все перекрывающиеся диапазоны, используя

SELECT o.*
FROM Schedules o
WHERE o.start < :new_end
AND o.end   > :new_start

2