Всем привет! Недавно мне пришлось решить следующую проблему: есть график работы трудовых ресурсов.
Например, график приема врача.
Оно формируется посредством правил и исключений.
Необходимо вычесть исключения из правил, но они периодические и не сразу понятно, в какой момент произойдет пересечение.
И чтобы все это работало быстро, нам пришлось призвать на помощь алгоритмы.
Например: врач Иванова О.
И.
открыт с 8:00 до 14:00 каждый день, кроме выходных.
Но однажды 5 июня 2020 года ей нужно уйти по семейным обстоятельствам с 8:00 до 10:00. Тогда она будет работать в это время на следующей неделе с 15:00 до 17:00. Тогда правила будут выглядеть так: Правила:
| 1.06.20 8:00 | 1.06.20 14:00 | Периодический | 1 день |
| 9.06.20 15:00 | 9.06.20 17:00 | Не периодический |
| 6.06.20 00:00 | 8.06.20 00:00 | Периодический | 1 неделя |
| 5.06.20 8:00 | 5.06.20 10:00 | Не периодический |
Получается, что для получения итогового графика нужно из верхних периодов времени вычесть нижние.
И здесь возможны 4 варианта.
Смотрите картинку ниже: 
Ищем решение
Первое решение, которое приходит в голову — сравнить каждое правило с каждым исключением и принять решение: отправлять его в результирующий график или нет. Но сравнение каждого с каждым выглядит как алгоритм сложности O(n 2 ).Не очень быстро.
Потом я наткнулся на алгоритм Бентли-Оттманн .
В оригинале предполагается найти пересечение прямых на плоскости.
Но у меня случай попроще: отрезки прямой.
Те.
у нас осталось только одно измерение.
Идея оригинального алгоритма Бентли-Оттмана заключается в движущейся строке сканирования, которая регистрирует события начала отрезка и конца отрезка.
А затем сравните вторую координату.
Но в моем случае линия сканирования идет слева направо и просто регистрирует события начала и окончания правил и исключений.
Вот как должен выглядеть результат графически (ниже): 
Описание алгоритма
Далее я расскажу, как адаптировать алгоритм Бентли-Оттмана под мою задачу.1. Начинаем сбор с событий.
Ээлемент коллекции будет выглядеть так
Тогда наше правило<DateTime, isRule, isOpen>
| 1.06.20 8:00 | 1.06.20 14:00 | Периодический | 1 день |
<1.06.20 8:00, True, True>
<1.06.20 14:00,True, False>
<2.06.20 8:00, True, True>
<2.06.20 14:00, True, False>
<3.06.20 8:00, True, True>
<3.06.20 14:00, True, False>
.
И исключение
| 6.06.20 00:00 | 8.06.20 00:00 | Периодический | 1 неделя |
<6.06.20 00:00, False, True>
<8.06.20 00:00, False, False>
<13.06.20 00:00, False, True>
<15.06.20 00:00, False, False>
.
2. Сортируем нашу коллекцию по первому аргументу DateTime. Это самая затратная часть алгоритма.
Потому что лучшая сложность сортировки — O(n log(n)) В результате мы получаем коллекцию событий, отсортированную по времени: как правил, так и исключений.
В нем содержится информация: когда произошло событие, является ли оно правилом или исключением, а также период открытия или закрытия.
3. Затем используйте цикл foreach для просмотра отсортированной коллекции.
Для каждого элемента коллекции мы примем ряд решений для формулирования результата.
На рисунке ниже показана блок-схема принятия решений.
Комментарии к блок-схеме: isRuleInAction — флаг, который устанавливается в значение True при запуске правила.
Когда правило заканчивается, ему присваивается значение False. isExclusionInAction — флаг, который устанавливается в значение True при возникновении исключения.
Когда исключение заканчивается, ему присваивается значение False. результатКандидат — переменная для хранения кандидата в результирующую коллекцию 4. В результате работы алгоритма получаем коллекцию отсортированных периодов времени.
Заключение
В более абстрактном варианте такой алгоритм можно использовать для пересечения не только временных отрезков, но и обычных отрезков на числовой прямой.Теги: #Алгоритмы #Bentley-Ottmann
-
Советы По Дизайну Брошюры
19 Oct, 24 -
Вмф
19 Oct, 24 -
Мой Крик Ярославны
19 Oct, 24 -
Квадрокоптер Своими Руками: Часть Ii.1
19 Oct, 24 -
Биокомпьютерная Музыка
19 Oct, 24
