Заметающая прямая: события, статус и одномерная разминка

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

Как думаешь, как это посчитать

В офисе восемь встреч на день, каждая - отрезок времени [начало, конец). Сколько переговорных нужно, чтобы никому не пришлось ждать? Это наибольшее число встреч, идущих одновременно. Вторая задача - на схеме платы 150 горизонтальных и 150 вертикальных дорожек; сколько пар пересекается?

Ответь себе до чтения: как решить первую задачу, не перебирая все моменты времени, и вторую - не перебирая все 22 500 пар? Подсказка одна на обе: представь, что идёшь по оси слева направо и смотришь только на то, что «открыто» в текущий момент. Для первой задачи ответ - 3 переговорные. Для второй - 66 пересечений, найденных за 2932 операции с деревом.

На что это похоже

Сканер документа. Световая полоса проходит лист сверху вниз и в каждый момент видит одну строку пикселей. Ей не нужно помнить весь лист - только то, что лежит под полосой, и то, что изменилось при сдвиге. Буква, которая только началась, добавляется к тому, что полоса «видит»; буква, которая кончилась, уходит.

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

Механизм: события, статус и инвариант

Алгоритм заметания собирается из двух структур:

СОБЫТИЯ   точки, где прямая останавливается,     начало и конец отрезка,
          упорядоченные по x                     точка пересечения
СТАТУС    что прямая пересекает сейчас,          активные отрезки,
          в удобном для запросов порядке         упорядоченные по y

Инвариант: когда прямая стоит в событии x, всё левее x уже обработано, а статус в точности описывает пересечение прямой с объектами. Событие меняет статус - добавляет или убирает объект - и задаёт вопрос, на который отвечает статус.

Встречи. Каждая встреча даёт два события: начало (+1) и конец (−1). Статус - одно число: сколько встреч идёт сейчас. Ответ - его максимум. При равном времени конец идёт раньше начала: встреча, кончившаяся в 10:00, освобождает комнату для встречи, начавшейся в 10:00. Порядок событий с одинаковой координатой - часть смысла задачи, а не деталь.

Горизонтальные и вертикальные отрезки. Прямая идёт по x. Горизонтальный отрезок на высоте y активен, пока прямая между его концами, - статус - набор активных высот с кратностью: две горизонтали на одной высоте дают в счётчике этой высоты двойку. Вертикальный отрезок на x от y₁ до y₂ пересекает ровно те активные горизонтальные, высота которых в [y₁, y₂]. Значит, статус должен быстро отвечать «сколько отмеченных высот в диапазоне» - это дерево Фенвика из главы о запросах на отрезке: добавление и сумма на префиксе за log N.

Правило

Заметание: отсортируй события по координате, задай порядок для равных координат по смыслу задачи и обрабатывай события по одному, поддерживая статус - пересечение прямой с объектами. Каждое событие меняет статус или задаёт ему вопрос. Время - n · log n на сортировку плюс стоимость операций со статусом.

Разбор: сколько нужно переговорных

# встречи [начало, конец) в минутах от 9:00
vstrechi = [[0, 60], [30, 90], [45, 50], [60, 120], [70, 80],
            [85, 95], [100, 130], [125, 140]]
sobytiya = []
for v in vstrechi:
    sobytiya.append([v[0], 1])
    sobytiya.append([v[1], -1])
# при равном времени -1 идёт раньше +1: встреча, кончившаяся
# в 60, освобождает комнату для встречи, начавшейся в 60
sobytiya.sort()
seychas = 0
maks = 0
kogda = 0
for s in sobytiya:
    seychas = seychas + s[1]
    if seychas > maks:
        maks = seychas
        kogda = s[0]
print(len(sobytiya), maks, kogda)

16 3 45

Шестнадцать событий, максимум три встречи одновременно, впервые - на 45-й минуте, то есть в 9:45: идут [0, 60), [30, 90) и [45, 50). Сортировка пар [время, ±1] сама ставит −1 раньше +1 при равном времени - так и задумано. Если бы правило было обратным, в 10:00 встреча [0, 60) ещё не освободила бы комнату, а [60, 120) уже заняла бы, и счётчик на мгновение показал бы лишнюю.

Перебором это решалось бы так: для каждого момента начала посчитать, сколько встреч идёт, - n². Заметание - сортировка и один проход.

Разбор: пересечения на плате

150 горизонтальных и 150 вертикальных дорожек на поле 1000 × 1000. Три вида событий по x: начало горизонтального отрезка, вертикальный отрезок, конец горизонтального. При равном x порядок именно такой: отрезки замкнуты, и касание концом засчитывается как пересечение.

import random
schet = [0]

def dobavit(derevo, i, d):
    i = i + 1
    while i < len(derevo):
        schet[0] = schet[0] + 1
        derevo[i] = derevo[i] + d
        i = i + (i & -i)

def summa(derevo, i):
    # сколько отмеченных значений y среди 0..i
    s = 0
    i = i + 1
    while i > 0:
        schet[0] = schet[0] + 1
        s = s + derevo[i]
        i = i - (i & -i)
    return s

random.seed(4)
N = 1000
gor = []
ver = []
for k in range(150):
    x1 = random.randint(0, N - 100)
    dlina = random.randint(10, 100)
    gor.append([x1, x1 + dlina, random.randint(0, N - 1)])
    y1 = random.randint(0, N - 100)
    x = random.randint(0, N - 1)
    ver.append([x, y1, y1 + random.randint(10, 100)])

# события по x: начало горизонтального (0), вертикальный (1), конец (2)
sobytiya = []
for g in gor:
    sobytiya.append([g[0], 0, g[2]])
    sobytiya.append([g[1], 2, g[2]])
for v in ver:
    sobytiya.append([v[0], 1, v[1], v[2]])
sobytiya.sort()
derevo = [0] * (N + 1)
otvet = 0
for s in sobytiya:
    if s[1] == 0:
        dobavit(derevo, s[2], 1)
    elif s[1] == 2:
        dobavit(derevo, s[2], -1)
    else:
        otvet = otvet + summa(derevo, s[3]) - summa(derevo, s[2] - 1)
pary = 0
for g in gor:
    for v in ver:
        if g[0] <= v[0] <= g[1] and v[1] <= g[2] <= v[2]:
            pary = pary + 1
print(otvet, pary, schet[0], len(gor) * len(ver))

66 66 2932 22500

Заметание и перебор согласны: 66 пересечений. Заметание сделало 2932 шага по дереву Фенвика на 450 событий - добавление стоит около log₂ 1000 ≈ 10 шагов, запрос вертикали - две суммы, - а перебор проверил 22 500 пар. Запрос считает «высоты не больше y₂» минус «высоты не больше y₁ − 1»; при y₁ = 0 вторая сумма пустая и равна нулю. При тысяче дорожек каждого вида это около 20 тысяч шагов дерева (те же 6-7 шагов на событие) против миллиона пар - разница примерно в пятьдесят раз, при миллионе - в десятки тысяч раз: n · log N против n².

Где кончается этот приём. Он считает пересечения, но не перечисляет их - если пересечений миллиард, otvet получит число, а список занял бы миллиард строк. И он держится на том, что отрезки горизонтальные и вертикальные: статус - набор чисел, и порядок в нём не меняется. У наклонных отрезков порядок по y меняется ровно в точках пересечения - этим займутся следующие уроки.

Что ломается без этого

Порядок равных событий наугад. Встречи [0, 60) и [60, 120) при «начало раньше конца» требуют двух комнат. Отрезок, касающийся вертикали концом, то теряется, то засчитывается - смотря кто встал раньше.

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

Сортировка без всех событий. Конец отрезка забыли превратить в событие - и отрезок навсегда остаётся в статусе, а ответ растёт.

Зачем это в работе

Календарь считает, сколько переговорных занято в пик. База данных отвечает «какие брони пересекаются с этой датой» тем же порядком событий. Проверка правил проектирования микросхем идёт по дорожкам, которые почти все горизонтальные и вертикальные, - и там заметающая прямая со статусом-деревом стоит в основе инструментов. Рендеринг векторной графики заполняет фигуры построчно: строка развёртки - заметающая прямая, статус - рёбра, которые она сейчас пересекает.

Теперь сам

1. Встречи [0, 30), [10, 20), [20, 40), [30, 50). Сколько комнат нужно и в какой момент впервые достигается максимум?
2. Горизонтальный отрезок от x = 5 до x = 9 на высоте 3 и вертикальный на x = 9 от y = 0 до y = 3. Какие события и в каком порядке, если касание засчитывается?
3. Почему в статусе для второй задачи хватает дерева Фенвика по y, а сбалансированное дерево не нужно?