Пересечения встреч: как мы убрали O(n²) из календаря

17 марта 2026 · бэкенд и календарь

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

Где именно сломалось

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

В феврале нам отдали большой офис с общей переговоркой на первом этаже, куда бронируют всё подряд: дейли, интервью, звонки на двадцать минут. В марте там оказалось 900 записей за месяц. Перебор пар — это 900 × 899 / 2 ≈ 404 тысячи сравнений на один запрос, плюс аллокации на каждую найденную пару. p99 месячного вида уехал с 40 мс до 1,9 с, и это ещё до того, как кто-то нажал «следующий месяц» три раза подряд.

Симптом был честный: страница просто думала. Никаких таймаутов, никаких ошибок в логах, только медленный рост p99 в графике, который мы неделю списывали на соседний сервис.

Что делал старый код

Ровно то, что написал бы любой на второй день жизни проекта — и это было правильно:

// Возвращает все пары пересекающихся броней одной комнаты.
func overlappingPairs(bs []Booking) []Pair {
    var out []Pair
    for i := 0; i < len(bs); i++ {
        for j := i + 1; j < len(bs); j++ {
            // Полуинтервалы [start, end): встреча 10:00–11:00
            // и встреча 11:00–12:00 не конфликтуют.
            if bs[i].Start.Before(bs[j].End) && bs[j].Start.Before(bs[i].End) {
                out = append(out, Pair{bs[i].ID, bs[j].ID})
            }
        }
    }
    return out
}

Условие пересечения здесь верное, и мы его не трогали: a.start < b.end && b.start < a.end — это классическая проверка для полуинтервалов, она же корректно отрабатывает вложенные встречи. Плохой была не логика, а то, что мы сравнивали каждую бронь с каждой, включая январскую с декабрьской.

Заметающая прямая

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

type evt struct {
    t     time.Time
    open  bool  // true — начало брони, false — конец
    id    int64
}

func overlappingPairs(bs []Booking) []Pair {
    ev := make([]evt, 0, len(bs)*2)
    for _, b := range bs {
        ev = append(ev, evt{b.Start, true, b.ID}, evt{b.End, false, b.ID})
    }
    // Концы обрабатываем раньше начал в одной точке:
    // встреча 10:00–11:00 не конфликтует с 11:00–12:00.
    sort.Slice(ev, func(i, j int) bool {
        if !ev[i].t.Equal(ev[j].t) {
            return ev[i].t.Before(ev[j].t)
        }
        return !ev[i].open && ev[j].open
    })

    active := make(map[int64]struct{}, 8)
    out := make([]Pair, 0, 16)
    for _, e := range ev {
        if !e.open {
            delete(active, e.id)
            continue
        }
        for other := range active {
            out = append(out, Pair{other, e.id})
        }
        active[e.id] = struct{}{}
    }
    return out
}

Сложность — O(n log n) на сортировку плюс O(k) на вывод, где k — реальное число пересечений. В нашем календаре k почти всегда равен нулю или единице: люди редко бронируют одну комнату дважды, а если бронируют, то один раз. Именно поэтому квадрат был так обиден — мы платили за 404 тысячи сравнений, чтобы вернуть пустой список.

Отдельно про порядок событий при равных временах. Если обрабатывать начала раньше концов, встреча 10:00–11:00 и встреча 11:00–12:00 окажутся конфликтом. Мы на этом уже обжигались год назад в другом месте, поэтому сортировка сразу написана «концы первыми», а в тестах лежит именно этот случай.

Слой базы: ограничение вместо проверки

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

Это чинится не алгоритмом, а базой:

CREATE EXTENSION IF NOT EXISTS btree_gist;

ALTER TABLE booking
  ADD CONSTRAINT booking_no_overlap
  EXCLUDE USING gist (
    room_id WITH =,
    tstzrange(starts_at, ends_at, '[)') WITH &&
  )
  WHERE (status = 'confirmed');

Теперь конкурентная вставка получает 23P01 exclusion_violation, который мы переводим в понятную ошибку интерфейса. Проверка в приложении осталась, но её роль изменилась: она нужна, чтобы показать человеку конфликт до отправки формы, а не чтобы гарантировать целостность. Гарантирует база.

Цифры

Чего мы не стали делать

• Интервальное дерево. Рассматривали всерьёз: оно даёт O(log n + k) на запрос «что пересекается с этим отрезком». Но у нас нет сценария с тысячами точечных запросов по живому индексу — мы всегда считаем целый месяц целиком. Дерево пришлось бы поддерживать в актуальном состоянии при каждой правке, а выигрыш относительно сортировки был бы в пределах шума. Сложность без выигрыша не берём.
• Кеш результата. Заманчиво, но инвалидировать его надо на любую правку любой брони месяца, а правок у нас больше, чем чтений в пике. 34 мс не стоят такого узла.
• Материализованное представление. Обсуждали десять минут и закрыли: обновление отстаёт, а пользователь ждёт увидеть свою бронь сразу после сохранения.

Что из этого забираем

Квадратичный алгоритм на маленьких данных — нормальное инженерное решение, а не долг. Ошибкой было другое: у нас не стояло алерта на размер входа. Мы узнали про 900 броней в комнате из графика latency, а не из метрики «максимальное число броней на комнату в месяц», которой просто не было. Теперь она есть, и алерт срабатывает на 2 000 — задолго до того, как что-нибудь начнёт тормозить.