Как найти максимальный размер команды по пересечению интервалов

Максимальный размер команды по пересечению интервалов: от наивного O(N^2) к O(N log N) с деревом Фенвика и сжатием координат, учтены включенные границы.

Когда графики пересекаются, из сотрудников можно собрать команды. Задача формулируется просто: даны моменты начала и окончания работы N сотрудников, при этом интервалы включают границы с обеих сторон. Требуется найти максимальный размер команды, в которой каждый участник пересекается по времени с одним конкретным человеком из этой группы. Для примера startTime = [2,5,6,8] и endTime = [5,6,10,9] ответ равен 3.

Краткое описание задачи

Даны два массива одинаковой длины: времена начала и окончания. Сотрудники могут объединиться, если их рабочие интервалы пересекаются; соприкосновение ровно по границе тоже считается пересечением. Размер команды для конкретного сотрудника — это число сотрудников, чьи интервалы пересекаются с его интервалом, плюс он сам. Цель — максимальный размер команды по всем сотрудникам. Иными словами, от группы не требуется попарного пересечения всех интервалов: достаточно, чтобы все интервалы в группе пересекались с одним определённым интервалом внутри группы.

Наивная реализация, которая не укладывается по времени

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

begins = [2,5,6,8]
finishes = [5,6,10,9]
m = len(begins)
best = 0
for a in range(m):
    cur = 0
    for b in range(m):
        if a == b:
            continue
        if ((begins[a] <= begins[b] <= finishes[a]) or (begins[a] <= finishes[b] <= finishes[a])):
            cur += 1
    best = max(best, cur)
print(best + 1)

Для примера код выводит правильное значение, но вложенный цикл работает за O(N²), что неприемлемо для больших входных данных.

Почему это медленно

Грубой перебор сопоставляет каждый интервал с каждым другим. Хотя проверка пересечения — операция O(1), именно количество сравнений «съедает» время. Чтобы масштабироваться, нужно сократить число сравнений и считать пересечения более эффективно.

Оптимизированный подход за O(N log N)

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

from bisect import bisect_left as bleft
import itertools as it
def max_team(begins: list[int], finishes: list[int]):
    coords = sorted(begins + finishes)
    tree = [0] * len(coords)
    def add(pos, val):
        while pos < len(tree):
            tree[pos] += val
            pos |= pos + 1
    def pref(pos):
        acc = 0
        while pos >= 0:
            acc += tree[pos]
            pos = (pos & (pos + 1)) - 1
        return acc
    order = sorted(range(len(finishes)), key=lambda k: begins[k])
    left_cnt = [0] * len(finishes)
    for _, grp in it.groupby(order, key=lambda k: begins[k]):
        seq = list(grp)
        for idx in seq:
            left_cnt[idx] = pref(len(tree) - 1) - pref(bleft(coords, begins[idx]) - 1)
        for idx in seq:
            add(bleft(coords, finishes[idx]), 1)
    tree = [0] * len(tree)
    peak = 0
    for _, grp in it.groupby(reversed(order), key=lambda k: begins[k]):
        seq = list(grp)
        for idx in seq:
            add(bleft(coords, begins[idx]), 1)
        for idx in seq:
            total = left_cnt[idx] + pref(bleft(coords, finishes[idx]))
            if total > peak:
                peak = total
    return peak
# Проверка на примере
print(max_team([2,5,6,8], [5,6,10,9]))  # ожидается: 3

Эта реализация работает за O(N log N). Для каждого интервала она считает, сколько интервалов пересекают его слева и справа, учитывая включённые границы, и возвращает максимальный размер команды. На приведённом примере результат — 3.

Зачем это нужно

Задачи на пересечение интервалов встречаются в планировании, распределении ресурсов, анализе логов и мониторинге в реальном времени. Разница между O(N²) и O(N log N) отделяет прототипы от производственных решений. Дерево Фенвика со сжатием координат — полезный приём, когда требуются быстрые префиксные суммы по значениям из большого или произвольного диапазона.

Выводы

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