Какой алгоритм использовать лля определения доступности временного промежутка?

Question

[Кирилл Сидоров]

Разрабатываю систему предварителтной записи через сайт. Сейчас столкнулся с проблемой, не могу придумать как красиво и правильно определить доступно или занято нужное время.
Немного подробностей:
Есть сущность "Запись", у которой два основных параметра: время и продолжительность.
Допустим, есть две таких сущности: (9:00, 30 мин), (10:00, 1 час). Понятно, что (9:35, 1 час) уже будет невалидным, так как на 10 уже есть запись.
Подскажие, какой алгоритм можно использовать? Не прошу код, просто пните в нужном направлении.

Answer 1

[Rsa97]

Поразмыслив пришёл к варианту:

SELECT count(*) AS x FROM records 
    WHERE (begin BETWEEN '{$newRecordBegin}' AND '{$newRecordEnd}') OR
          ('{$newRecordBegin}' BETWEEN begin AND end)

Первая часть условия - начало какой-либо старой записи попадает в середину новой.
Вторая часть - начало новой записи попадает в середину какой-либо старой .
Если хоть одно условие выполнено - count(*) > 0, вставлять запись нельзя.

Answer 2

[sasha]

на вскидку пришло в голову хранить в безе время начала и время конца и потом уже просто одним SQL запросом выяснять свободно или нет

Comments

[Кирилл Сидоров]

Вот меня эта "математика" и интересует. Сейчас значения сущностей переводятся в массив интервалов по шкале времени и в цикле проверка принадлежности точек проверяемой сущности интервалам из БД средствами ЯП, но не БД. Но может есть более красивое решение.

[alternativshik]

храните начало и конец и потом можно просто найти 1 запросом к бд, либо найти пересечение отрезков средствами ЯП.

[alternativshik]

P.S. хранить в данном случае очень удобно в timestamp - у вас будет и дата и время, и получить продолжительность сможете и найти легко пересечения.

[sasha]

@cyberia держи хинт:
start || end
9 || 9.30
нужно вписать новую запись на час в 9
SELECT * FROM table WHERE start>=9 AND (start<=10 OR (end<=10 AND end>9))
время желательно хранить в timestamp. этот запрос должен выдавать можно ли вписать встречу которая начнется в 9 и закончится в 10

Answer 3

[Rsa97]

0. Пытаемся вставить новую запись newRecordStart, newRecordLength
1. Получаем две ближайшие по времени записи, одну до (prevRecordStart, prevRecordLength) и одну после новой (nextRecordStart, nextRecordLength).
2. Новая запись не должна пересекаться с предыдущей:
(newRecordStart >= prevRecordStart+prevRecordLength)
3. Новая запись не должна пересекаться со следующей:
(newRecordStart+newRecordLength <= nextRecordStart)
4. Если оба условия выполнены - можно вставлять запись.