Проверка конфликтов расписания iOS: полуоткрытые интервалы

В списке бронирований две встречи идут вплотную друг за другом, но при сохранении система сообщает о конфликте. В другом случае одна длинная бронь полностью охватывает три короткие, а на странице статистики максимальное число одновременных бронирований равно одному. Ни в том, ни в другом случае не обязательно начинать с интерфейса. На облачном Mac можно вынести расчёт интервалов в чистые функции Swift, зафиксировать граничные условия и ожидаемые результаты, а затем свести ошибку к воспроизводимому набору входных данных. Здесь речь идёт о времени занятости одного ресурса, а не об отображении дат или сетевых запросах.

Сначала задайте правила полуоткрытых интервалов

Представим каждую бронь интервалом [start, end): начало включено, конец — нет. Поэтому [0, 10) и [10, 20) не конфликтуют, а [0, 10) и [9, 20) — конфликтуют. Время можно измерять в секундах или минутах, но в рамках одного расчёта единицы должны быть одинаковыми: нельзя напрямую смешивать значения разной точности.

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

Объединение интервалов занятости и поиск максимального числа одновременно занятых слотов — разные задачи. При объединении теряется информация о количестве наложений, поэтому сначала объединить интервалы, а затем посчитать одновременные бронирования нельзя.

Если между встречами по правилам нужен запас времени на подготовку, сначала включите его в интервал занятости, а затем применяйте те же правила. Дополнительная проверка только на уровне интерфейса приведёт к тому, что список и API сохранения будут давать разные ответы.

Напишите реализацию, которую можно запустить отдельно

Сохраните следующий код в Intervals.swift. Он использует только стандартную библиотеку. При объединении соединяются лишь действительно пересекающиеся интервалы; соприкосновение границ пересечением не считается. Целочисленные отметки времени здесь нужны, чтобы сначала отделить алгоритм от преобразования дат.

typealias Slot = Range<Int>

func merged(_ input: [Slot]) -> [Slot] {
    precondition(input.allSatisfy { !$0.isEmpty })
    let sorted = input.sorted {
        if $0.lowerBound == $1.lowerBound {
            return $0.upperBound < $1.upperBound
        }
        return $0.lowerBound < $1.lowerBound
    }
    var result: [Slot] = []
    for slot in sorted {
        if let last = result.last,
           slot.lowerBound < last.upperBound {
            result[result.count - 1] =
                last.lowerBound..<max(last.upperBound, slot.upperBound)
        } else {
            result.append(slot)
        }
    }
    return result
}

func peak(_ input: [Slot]) -> Int {
    precondition(input.allSatisfy { !$0.isEmpty })
    let events = input.flatMap {
        [(time: $0.lowerBound, delta: 1),
         (time: $0.upperBound, delta: -1)]
    }.sorted {
        if $0.time == $1.time {
            return $0.delta < $1.delta
        }
        return $0.time < $1.time
    }
    var active = 0
    var maximum = 0
    for event in events {
        active += event.delta
        maximum = max(maximum, active)
    }
    return maximum
}

precondition(merged([]).isEmpty)
precondition(peak([]) == 0)
precondition(merged([0..<10, 10..<20]) == [0..<10, 10..<20])
precondition(peak([0..<10, 10..<20]) == 1)
precondition(merged([0..<10, 5..<15, 10..<20]) == [0..<20])
precondition(peak([0..<10, 5..<15, 10..<20]) == 2)
precondition(merged([0..<30, 5..<10, 8..<12]) == [0..<30])
precondition(peak([0..<30, 5..<10, 8..<12]) == 3)
precondition(peak([0..<10, 0..<10]) == 2)

Запустите в терминале:

xcrun swift Intervals.swift

Если все проверки пройдены, вывода не будет, а код завершения будет равен нулю. Использование precondition вместо одних лишь assert не даёт тестам превратиться в формальность после отключения утверждений в обычной оптимизированной сборке. В проверочном скрипте также не следует использовать параметры компиляции, отключающие проверки безопасности.

Проверьте события в один момент времени и вложенные интервалы

В алгоритме сканирующей прямой начало интервала даёт плюс один, а конец — минус один. Для событий с одинаковой временной отметкой сначала обязательно выполняется вычитание, затем сложение. Иначе две соседние брони на мгновение будут учтены как одновременные. Сортировка только по времени, без явного порядка для совпадающих отметок, — типичный источник граничных ошибок.

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

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

Сверьте результат с независимым расчётом

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

func referencePeak(_ input: [Slot]) -> Int {
    guard let start = input.map(\.lowerBound).min(),
          let end = input.map(\.upperBound).max() else {
        return 0
    }
    return (start..<end).map { tick in
        input.filter { $0.contains(tick) }.count
    }.max() ?? 0
}

let candidates: [Slot] = (0..<5).flatMap { start in
    ((start + 1)...5).map { start..<$0 }
}

for first in candidates {
    for second in candidates {
        let sample = [first, second]
        precondition(peak(sample) == referencePeak(sample))
        precondition(merged(sample) ==
                     merged(Array(sample.reversed())))
        precondition(merged(merged(sample)) == merged(sample))
    }
}

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

Перед интеграцией уточните проверку входных данных и состав отчёта об ошибке

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

Если общий список содержит бронирования нескольких переговорных, сначала сгруппируйте их по идентификатору ресурса, а затем выполните расчёт для каждой группы отдельно. Встречи, проходящие одновременно в разных комнатах, не должны конфликтовать между собой. Если требуется исключить и одновременное участие одного человека в нескольких встречах, задайте для людей отдельный набор ресурсных ограничений. Не смешивайте безусловно все бронирования в одном проходе сканирующей прямой.

Для записи сбоя достаточно сохранить идентификатор ресурса, нормализованные интервалы, ожидаемое и фактическое значения, а также версию набора инструментов. Информация об участниках не нужна. Прежде чем исправлять ошибку, добавьте вызвавшие её данные в фиксированный набор тестов, затем выполните весь скрипт. Итоговый критерий успеха — согласованность граничных тестов, эталонного расчёта и группировки по бизнес-правилам, а не просто исчезновение сообщения о конфликте на одном из экранов.

Часто задаваемые вопросы