Расчет доступности вещей за промежуток времени

Question

следующая ситуация: у нас есть 3 вещи, доступные одновременно.Первый забронирован с 09:00 до 11:00.Второй заказан с 11:00 до 13:00. Я хочу подсчитать, сколько вещей доступно с 10:00 до 12:00.Я сделал это, посчитав, сколько вещей забронировано в диапазоне с 10:00 до 12:00.Было 2. Итак, доступны вещи 1. Но первое и второе могут быть одинаковыми.Таким образом, в назначенное время доступно 2, и мой расчет был неверным.

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

 $blocks = array();
    $times = array();
    foreach($results as $result){
     $block = array();
     $block['start'] = DateTime::createFromFormat("Y-m-d H:i:s",   $result['start'])->getTimestamp();
        $block['end'] = DateTime::createFromFormat("Y-m-d H:i:s", $result['end'])->getTimestamp();
        $block['things'] = $result['cnt'];
        $blocks[] = $block;
        $times[] = $block['start'];
        $times[] = $block['end'];
    }

    $times = array_unique($times);
    $times = array_values($times);
    $peak = 0;

    foreach($times as $time){
        $timePeak = 0;
        foreach($blocks as $block){

            if($time >= $block['start'] && $time <= $block['end']){
                $timePeak += $block['things'];
            }
        }
        if($timePeak > $peak){
            $peak = $timePeak;
        }
    }

    return $peak;
}

с помощью этого метода я создаю временные метки для каждого времени начала и окончания каждого бронирования в этом диапазоне.Затем я вычислил сумму всех бронирований каждой отметки времени.Максимум расчетов (пик) был максимальным количеством бронирований.Таким образом, доступны вещи макс - пик.

Это работает.Но есть ли более элегантный способ рассчитать его?

Answer 1

Первое, что следует отметить при бронировании, - это то, что вы перекрываете время.

Если бронирование на один час регистрируется как начинающееся с 10:00:00 и заканчивающееся на 11:00:00, это на самом деле длится 1 час и 1 секунду.

Чтобы учесть это и предотвратить неправильные совпадения, я вычитал 1 секунду из дат перед сравнением. Это казалось самым простым способом решения проблемы.

SELECT b.*
FROM bookings b
WHERE (DATE_SUB(@start, INTERVAL 1 SECOND) BETWEEN start AND DATE_SUB(end, INTERVAL 1 SECOND))
OR (DATE_SUB(@end, INTERVAL 1 SECOND) BETWEEN start AND DATE_SUB(end, INTERVAL 1 SECOND));

В приведенном выше примере замените @start и @end привязками параметров запроса для времени начала и окончания.

Пример скрипта БД .

Answer 2

Похоже на эту распространенную проблему интервью: https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/

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

Чтобы обработать граничный случай, о котором вы говорили, где окончание бронирования совпадает с началом бронирования, убедитесь, что сортировка «начинается» и «заканчивается» всегда сортирует «конец» перед «началом», когда время то же самое, чтобы у вас не возникало совпадения, когда его не существует на самом деле.

Я предполагаю, что вы работаете за таким столом:

CREATE TABLE `bookings` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `start` datetime NOT NULL,
  `end` datetime NOT NULL,
  PRIMARY KEY (`id`)
);

И у вас есть такие данные:

INSERT INTO `bookings` (`id`, `start`, `end`)
VALUES
    (1, '2019-05-05 09:00:00', '2019-05-05 11:00:00'),
    (2, '2019-05-05 11:00:00', '2019-05-05 13:00:00'),
    (3, '2019-05-05 07:00:00', '2019-05-05 10:00:00'),
    (4, '2019-05-05 12:00:00', '2019-05-05 14:00:00'),
    (5, '2019-05-05 14:00:00', '2019-05-05 17:00:00'),
    (6, '2019-05-05 10:30:00', '2019-05-05 11:30:00');

В этих данных есть все соответствующие случаи, которые необходимо рассмотреть:

1. Бронирования, заканчивающиеся до вашего диапазона
2. Бронирования, начинающиеся после вашего диапазона
3. Бронирования, которые пересекают начало вашего диапазона
4. Бронирования, которые пересекают конец вашего диапазона
5. Заказы содержатся полностью в пределах вашего диапазона
6. Бронирования, которые "передаются" в пределах вашего диапазона

Я посмотрел на создание SQL-запроса для этого, но остановился, когда он стал более сложным, чем вы на самом деле хотели бы кодировать в SQL. Я думаю, что это, вероятно, выполнимо, но требует действительно ужасного SQL. Определенно сделайте это в коде. Я думаю, что алгоритм состоит в том, чтобы загрузить все заказы, относящиеся к вашему диапазону, с помощью запроса вроде:

SELECT * FROM bookings 
WHERE start BETWEEN :start AND :end
     OR end BETWEEN :start AND :end

Это все заказы, которые могут иметь значение. Затем вы сортируете начальные и конечные события как отдельные события, как описано ранее, и перебираете список событий, сохраняя счетчик хода и максимальное значение, видимое до сих пор. Счетчик хода сначала увеличивается, а в конце возвращается к нулю, но может иметь несколько пиков в середине. Таким образом, вы не можете просто остановить первый раз, когда он выходит из строя, вы должны продолжать сканирование до тех пор, пока не пройдете все события (или, по крайней мере, до вашего конечного времени, но проще и без реальных затрат, чтобы просто пройти весь путь через список). Когда вы закончите, вы получите максимальное количество одновременных заказов.

Я не проверял и не компилировал это, поэтому воспринимайте это как псевдо-код. Я бы изменил ваш код на что-то вроде этого:

//assumedly, prior to this point you have a
//$startTime and $endTime that you used to do the query mentioned above
//and the results of the query are in $results

$times = array();
foreach($results as $result){
    $time = array();
    $time['time'] = DateTime::createFromFormat("Y-m-d H:i:s",   $result['start'])->getTimestamp();
    $time['change'] = $result['cnt'];
    $times[] = $time;
    $time['time'] = DateTime::createFromFormat("Y-m-d H:i:s", $result['end'])->getTimestamp();
    $time['change'] = -1 * $result['cnt'];
    $times[] = $time;
}

usort($times, function($lh, $rh) {
    if ($lh['time'] === $rh['time']) {
        return $lh['change'] - $rh['change']
    } else {
        return $lh['time'] < $rh['time'] ? -1 : 1;
    }
}

$maxPeak = 0;
$curVal = 0;
foreach($times as $time){
    //breaking early here isn't so much about optimization as it is about
    //dealing with the instantaneous overlap problem where something starts
    //right at the end time.  You don't want that to look like a utilization
    //that counts against you.
    if ($time['time'] === $endTime) {
        break;
    }

    $curVal += $time['change'];
    if ($curVal > $maxPeak) {
        $maxPeak = $curVal;
    }
}

//$maxPeak is the max number of things in use during the period