Sweep line: алгоритм заметающей прямой для интервалов, skyline и пересечений
Алгоритм заметающей прямой простыми словами: события, порядок сортировки при равных координатах, максимум одновременных интервалов, Skyline, пересечения отрезков и площадь прямоугольников.
Коротко
| Что | Суть |
|---|---|
| Идея | Двигаем воображаемую прямую слева направо и реагируем только на события — точки изменений |
| Событие | Пара «координата + что произошло»: интервал открылся, закрылся, пришёл запрос |
| Состояние | То, что знает прямая в текущей точке: счётчик, куча, дерево Фенвика, множество отрезков |
| Сложность | на сортировку событий плюс стоимость обновления состояния |
| Главная ловушка | Порядок событий с одинаковой координатой — он решает, касание это пересечение или нет |
| Где спрашивают | Meeting Rooms II, Skyline Problem, Number of Flowers in Full Bloom, Rectangle Area II |
Если вы уже решали «минимальное число переговорок» через отсортированные начала и концы — вы уже пользовались заметающей прямой. Базовые задачи на отрезки (слияние, вставка, пересечение двух расписаний) разобраны в статье про задачи на интервалы, здесь повторять их не будем. Эта статья — про сам приём: как его обобщить, где он ломается и как с ним решаются задачи уровня Hard.
Интуиция: смотрим только на точки изменений
Представьте ось времени и на ней сотню встреч. Вопрос: сколько встреч идёт одновременно в самый загруженный момент?
Наивный способ — перебрать все моменты времени и для каждого посчитать покрывающие его встречи. Если время целое и лежит в пределах , это безнадёжно. Даже если перебирать только концы встреч, получится : точек, и для каждой проход по всем встречам.
Наблюдение, на котором держится весь метод: между двумя соседними концами ничего не меняется. Число активных встреч может вырасти только в момент чьего-то начала и упасть только в момент чьего-то конца. Значит, достаточно:
- Превратить каждый объект в события — точки, где что-то меняется.
- Отсортировать события по координате.
- Пройти по ним один раз, поддерживая состояние «что сейчас пересекает прямую».
Вся разница между задачами — в том, что считать событием и какую структуру держать в качестве состояния. Для подсчёта хватает одного целого числа, для Skyline нужна куча, для пересечений отрезков — дерево Фенвика или сбалансированное дерево.
Шаблон: максимум одновременных интервалов
Начнём с самой простой формы. Интервалы полуоткрытые, [start, end): встреча [1, 5) и встреча [5, 8) не мешают друг другу.
def max_overlap(intervals: list[tuple[int, int]]) -> tuple[int, int | None]: """Максимум одновременно открытых полуоткрытых интервалов [start, end).""" events = [] for start, end in intervals: events.append((start, 1)) # открылся events.append((end, -1)) # закрылся # при равной координате -1 идёт раньше +1: [1, 5) и [5, 8) не пересекаются events.sort() active = best = 0 best_at = None for x, delta in events: active += delta if active > best: best, best_at = active, x return best, best_at max_overlap([(0, 30), (5, 10), (15, 20)]) # (2, 5) max_overlap([(1, 5), (5, 8), (2, 6)]) # (2, 2)
Функция возвращает не только максимум, но и момент, когда он достигается, — на собеседовании это частый follow-up: «а когда именно пик нагрузки?».
Разберём первый пример по шагам:
| Событие | active | best | Комментарий |
|---|---|---|---|
(0, +1) | 1 | 1 | началась встреча 0–30 |
(5, +1) | 2 | 2 | началась 5–10, пик |
(10, -1) | 1 | 2 | 5–10 закончилась |
(15, +1) | 2 | 2 | началась 15–20 |
(20, -1) | 1 | 2 | |
(30, -1) | 0 | 2 | все закончились |
Ответ 2 — это и есть Meeting Rooms II. В статье про интервалы та же задача решена двумя отдельно отсортированными массивами начал и концов. Это тот же свип, просто события хранятся в двух списках, а не в одном. Вариант с общим списком событий удобнее тем, что легко расширяется: событиям можно дать веса, типы и полезную нагрузку.
На JavaScript нужен явный компаратор — встроенный sort без него сравнивает строки:
function maxOverlap(intervals) { const events = [] for (const [start, end] of intervals) { events.push([start, 1], [end, -1]) } // по координате, при равенстве закрытие (-1) раньше открытия (+1) events.sort((a, b) => a[0] - b[0] || a[1] - b[1]) let active = 0 let best = 0 for (const [, delta] of events) { active += delta best = Math.max(best, active) } return best } maxOverlap([ [0, 30], [5, 10], [15, 20], ]) // 2 maxOverlap([ [1, 5], [5, 8], ]) // 1
Если у событий есть веса (пассажиры, нагрузка, потребляемая память), вместо +1/-1 пишем +w/-w. Так решается Car Pooling, и это ровно разностный массив, в котором хранятся только ненулевые ячейки. Когда координаты маленькие, массив проще; когда до — сортируем события.
Порядок событий при равной координате
Это место, где ломается большинство решений. Сортировка по координате однозначна, пока координаты разные. Как только в одной точке встречаются начало и конец, результат зависит от того, что обработать первым.
| Отрезки | Касание — пересечение? | Порядок в одной точке | Что ответит [1,5] и [5,8] |
|---|---|---|---|
Полуоткрытые [l, r) | нет | сначала закрытия | 1 |
Закрытые [l, r] | да | сначала открытия | 2 |
В Python кортежи сравниваются поэлементно, поэтому порядок задаётся вторым полем. Для полуоткрытых интервалов (x, -1) < (x, 1) получается автоматически. Для закрытых нужно, чтобы открытия шли раньше, — удобнее завести явные коды типов:
def max_overlap_closed(intervals: list[tuple[int, int]]) -> int: """То же для закрытых [start, end]: касание в точке — пересечение.""" events = [] for start, end in intervals: events.append((start, 0)) # 0 < 1: открытия раньше закрытий events.append((end, 1)) events.sort() active = best = 0 for _, kind in events: active += 1 if kind == 0 else -1 best = max(best, active) return best max_overlap_closed([(1, 5), (5, 8)]) # 2 max_overlap([(1, 5), (5, 8)]) # (1, 1)
Правило, которое стоит проговорить на собеседовании вслух: сначала договорись о границах, потом выбирай порядок событий. Если интервьюер говорит «встреча до 10:00 и встреча с 10:00 помещаются в одну комнату», интервалы полуоткрытые, и закрытия идут первыми.
Когда типов событий больше двух, порядок нужно продумать для каждой пары. Об этом следующая задача.
Запросы как события: Number of Flowers in Full Bloom
LeetCode 2251. Цветок i цветёт на отрезке [start_i, end_i] включительно. Люди приходят в моменты people[j]. Сколько цветов цветёт для каждого человека?
Наивно — . Свип даёт : добавляем запросы как третий тип событий. Когда прямая доходит до запроса, текущее значение счётчика и есть ответ.
Порядок в одной точке: цветок, распустившийся в момент t, уже виден; цветок, который отцветает в t, ещё виден. Значит, открытия → запросы → закрытия:
def full_bloom_flowers(flowers: list[list[int]], people: list[int]) -> list[int]: START, QUERY, END = 0, 1, 2 # порядок обработки при равном времени events = [] for s, e in flowers: events.append((s, START, -1)) events.append((e, END, -1)) for i, t in enumerate(people): events.append((t, QUERY, i)) # третье поле — индекс человека events.sort() answer = [0] * len(people) blooming = 0 for _, kind, i in events: if kind == START: blooming += 1 elif kind == END: blooming -= 1 else: answer[i] = blooming return answer full_bloom_flowers([[1, 6], [3, 7], [9, 12], [4, 13]], [2, 3, 7, 11]) # [1, 2, 2, 2]
Этот приём называется офлайн-обработкой запросов: мы знаем все запросы заранее, поэтому можем перемешать их с данными и ответить за один проход. Индекс в событии нужен, чтобы вернуть ответы в исходном порядке.
У этой задачи есть и решение без явного свипа: отсортировать начала и концы и для каждого t бинарным поиском посчитать (число начал ≤ t) − (число концов < t). Это тот же свип, только «замороженный» в два отсортированных массива — удобно, если запросы приходят онлайн.
from bisect import bisect_left, bisect_right def full_bloom_bisect(flowers: list[list[int]], people: list[int]) -> list[int]: starts = sorted(s for s, _ in flowers) ends = sorted(e for _, e in flowers) return [bisect_right(starts, t) - bisect_left(ends, t) for t in people]
Подробнее про bisect_left и bisect_right — в статье про бинарный поиск.
Состояние сложнее счётчика: Skyline Problem
LeetCode 218, Hard, одна из самых известных задач на свип. Даны здания [left, right, height]. Нужно вернуть контур силуэта: точки [x, h], где высота силуэта меняется.
Счётчика здесь мало. В каждой точке нужно знать максимальную высоту среди зданий, которые пересекает прямая. Максимум при вставках и удалениях — работа для кучи.
Сложность в том, что удалить произвольный элемент из heapq нельзя. Обходной путь — ленивое удаление: храним в куче пары (−высота, правый край) и, прежде чем читать вершину, выбрасываем здания, правый край которых уже позади.
import heapq def get_skyline(buildings: list[list[int]]) -> list[list[int]]: events = [] for left, right, height in buildings: events.append((left, -height, right)) # начало: высота со знаком минус events.append((right, 0, 0)) # конец: просто точка пересчёта # при равном x начала идут раньше концов, высокие — раньше низких events.sort() result = [] heap = [(0, float("inf"))] # (-высота, где кончается); земля не кончается for x, neg_h, right in events: if neg_h: heapq.heappush(heap, (neg_h, right)) # ленивое удаление: выкидываем здания, которые уже закончились while heap[0][1] <= x: heapq.heappop(heap) height = -heap[0][0] if not result or result[-1][1] != height: result.append([x, height]) return result get_skyline([[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]) # [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
Почему это работает, по пунктам:
- Событие конца ничего не кладёт в кучу. Оно нужно только для того, чтобы в этой точке прямая остановилась и пересчитала максимум. Само здание уберёт ленивое удаление.
- Ленивое удаление корректно. В куче могут лежать «мёртвые» здания, но мы чистим только вершину. Мёртвое здание не на вершине ни на что не влияет: максимум определяется вершиной, и она всегда живая после цикла
while. - Земля
(0, inf)гарантирует, что куча никогда не опустеет и после последнего здания высота станет 0. - Дубликаты отсекаются сравнением с последней высотой в ответе. Без него на входе
[[0, 2, 3], [2, 5, 3]]получилось бы[[0, 3], [2, 3], [5, 0]]вместо правильного[[0, 3], [5, 0]].
Порядок событий при равном x здесь тоже важен. Кортеж (x, -height, right) сортирует начала (отрицательное второе поле) раньше концов (ноль), а среди начал — высокие раньше низких. Попробуйте три здания с общим левым краем [[1, 2, 1], [1, 2, 2], [1, 2, 3]]: при обратном порядке в ответ сначала попала бы высота 1, потом 2, потом 3 — три точки с одинаковым x. С правильным порядком ответ [[1, 3], [2, 0]].
Сложность — : событий, каждое здание один раз попадает в кучу и один раз из неё выходит. В Java и C++ вместо ленивой кучи часто берут TreeMap/multiset с честным удалением — асимптотика та же. Подробнее про кучу и её ловушки — в статье про очередь с приоритетом.
Пересечения отрезков
Здесь sweep line родом — из вычислительной геометрии. Классическая постановка: дано отрезков на плоскости, нужно найти их пересечения.
Базовая проверка двух отрезков
Сначала нужен примитив: пересекаются ли два конкретных отрезка. Он строится на знаке векторного произведения — повороте тройки точек:
def orient(a, b, c) -> int: """1 — поворот против часовой, -1 — по часовой, 0 — точки на одной прямой.""" v = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) return (v > 0) - (v < 0) def on_segment(a, b, p) -> bool: return min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= p[1] <= max( a[1], b[1] ) def segments_intersect(p1, p2, p3, p4) -> bool: d1, d2 = orient(p3, p4, p1), orient(p3, p4, p2) d3, d4 = orient(p1, p2, p3), orient(p1, p2, p4) if d1 != d2 and d3 != d4: return True # коллинеарные случаи: конец одного отрезка лежит на другом return ( (d1 == 0 and on_segment(p3, p4, p1)) or (d2 == 0 and on_segment(p3, p4, p2)) or (d3 == 0 and on_segment(p1, p2, p3)) or (d4 == 0 and on_segment(p1, p2, p4)) ) segments_intersect((0, 0), (2, 2), (0, 2), (2, 0)) # True segments_intersect((0, 0), (1, 1), (2, 2), (3, 3)) # False
Отрезки пересекаются, если концы каждого лежат по разные стороны от прямой другого. Всё в целых числах — никаких погрешностей с плавающей точкой. Перебор всех пар даёт , и для до нескольких тысяч этого достаточно.
Горизонтальные и вертикальные: точный подсчёт за O(n log n)
Частный случай, который реально дают на собеседованиях и олимпиадах: отрезки только горизонтальные и вертикальные, нужно посчитать число пересечений. Пересечений может быть , но нам нужно только их количество.
Ведём вертикальную прямую слева направо. Состояние — множество координат горизонтальных отрезков, которые прямая сейчас пересекает. События:
- левый конец горизонтали — добавить её ;
- вертикаль на абсциссе — посчитать, сколько активных попадает в ;
- правый конец горизонтали — убрать её .
Запрос «сколько чисел в диапазоне» при вставках и удалениях — это дерево Фенвика по сжатым координатам. Порядок в одной точке для закрытых отрезков: добавления → запросы → удаления, чтобы касания концами считались.
from bisect import bisect_left, bisect_right class Fenwick: def __init__(self, n: int): self.t = [0] * (n + 1) def add(self, i: int, d: int) -> None: i += 1 while i < len(self.t): self.t[i] += d i += i & -i def prefix(self, i: int) -> int: # сумма на [0, i) s = 0 while i > 0: s += self.t[i] i -= i & -i return s def count_hv_intersections(horizontal, vertical) -> int: """horizontal: (x1, x2, y), vertical: (x, y1, y2); концы включительно.""" ys = sorted({y for _, _, y in horizontal}) # сжатие координат OPEN, QUERY, CLOSE = 0, 1, 2 events = [] for x1, x2, y in horizontal: events.append((x1, OPEN, y, 0)) events.append((x2, CLOSE, y, 0)) for x, y1, y2 in vertical: events.append((x, QUERY, y1, y2)) events.sort() bit = Fenwick(len(ys)) total = 0 for _, kind, a, b in events: if kind == OPEN: bit.add(bisect_left(ys, a), 1) elif kind == CLOSE: bit.add(bisect_left(ys, a), -1) else: # сколько активных горизонталей с y в [a, b] total += bit.prefix(bisect_right(ys, b)) - bit.prefix(bisect_left(ys, a)) return total count_hv_intersections([(0, 4, 1), (1, 3, 3)], [(2, 0, 4), (4, 1, 1), (5, 0, 9)]) # 3
Сжатие координат нужно, потому что может быть до , а дерево Фенвика индексируется плотно. Сортируем уникальные и заменяем значение его позицией — bisect_left. Для границ запроса y1 и y2, которых может не быть среди горизонталей, bisect_left и bisect_right дают ровно нужный полуинтервал индексов.
Итого : сортировка событий и по одной операции Фенвика на событие. Вместо Фенвика подойдёт и дерево отрезков, если нужно что-то кроме суммы.
Общий случай: Shamos–Hoey и Bentley–Ottmann
Для произвольных отрезков идея та же, но состояние хитрее: активные отрезки хранятся упорядоченными по в текущей точке прямой, обычно в сбалансированном дереве поиска.
- Shamos–Hoey (1976) отвечает на вопрос «есть ли хоть одно пересечение» за . Ключевое наблюдение: если два отрезка пересекаются, то перед точкой пересечения они в какой-то момент становятся соседями в порядке по . Поэтому при вставке отрезка достаточно проверить его с двумя соседями, а при удалении — проверить друг с другом соседей удалённого.
- Bentley–Ottmann (1979) находит все пересечений за . Точки пересечения сами становятся событиями: в них два отрезка меняются местами в порядке по . События держат в очереди с приоритетом, потому что новые появляются по ходу свипа.
Писать Bentley–Ottmann на собеседовании никто не попросит: вырожденные случаи (вертикальные отрезки, три отрезка через одну точку, совпадающие концы) превращают его в сотни строк. Но знать идею полезно — это частый теоретический вопрос на позиции, связанные с геометрией, картами и CAD.
Площадь объединения прямоугольников
LeetCode 850, Rectangle Area II. Даны прямоугольники [x1, y1, x2, y2], нужно найти площадь их объединения, перекрытия считаются один раз.
Ведём вертикальную прямую по . Между двумя соседними событиями набор прямоугольников под прямой не меняется, значит, на этой полосе покрытая высота постоянна. Площадь полосы — ширина, умноженная на длину объединения -отрезков активных прямоугольников. А объединение отрезков — задача слияния интервалов из соседней статьи.
def rectangle_area(rectangles: list[list[int]]) -> int: events = [] for x1, y1, x2, y2 in rectangles: events.append((x1, 1, y1, y2)) events.append((x2, -1, y1, y2)) events.sort() active = [] # y-отрезки прямоугольников, которые пересекает прямая area = 0 prev_x = events[0][0] for x, kind, y1, y2 in events: # полоса [prev_x, x] покрыта по y объединением активных отрезков covered = 0 cur_end = float("-inf") for a, b in sorted(active): a = max(a, cur_end) if b > a: covered += b - a cur_end = b area += covered * (x - prev_x) if kind == 1: active.append((y1, y2)) else: active.remove((y1, y2)) prev_x = x return area % (10**9 + 7) rectangle_area([[0, 0, 2, 2], [1, 0, 2, 3], [1, 0, 3, 1]]) # 6
Обратите внимание на порядок действий внутри цикла: сначала считаем площадь полосы, которая закончилась на текущем x, потом обновляем состояние. Перепутать — значит прибавить полосу с неправильным набором прямоугольников.
Сложность — : на каждом из событий сортируем до отрезков. В LeetCode , этого хватает с запасом. Если до , длину объединения поддерживают деревом отрезков по сжатым : каждый узел хранит, сколько прямоугольников покрывают его целиком, и длину покрытой части. Тогда общая сложность — это классическая олимпиадная задача.
Сложность: сводка
| Задача | События | Состояние | Время |
|---|---|---|---|
| Максимум одновременных | начало, конец | счётчик | |
| Ответы для точек-запросов | начало, запрос, конец | счётчик | |
| Skyline | левый и правый край | куча с ленивым удалением | |
| Пересечения H/V-отрезков | концы горизонталей, вертикали | дерево Фенвика по | |
| Есть ли пересечение (общий случай) | концы отрезков | дерево поиска по | |
| Площадь прямоугольников | левый и правый край | список или дерево отрезков | / |
Память во всех случаях на события и состояние.
Типичные ошибки
- Не продуман порядок при равных координатах. Решение проходит примеры и падает на касаниях. Перед кодом выпишите для каждой пары типов событий, кто идёт первым, и почему.
- Сортировка без компаратора в JavaScript.
[[10, 1], [9, 1]].sort()сравнивает строки, и10окажется раньше9. - Обновление состояния до подсчёта ответа. В задачах с площадью или длиной сначала учитываем отрезок между предыдущим и текущим событием, потом применяем событие.
- Попытка удалять из
heapqпо значению.heap.remove(x)ломает инвариант кучи и стоит . Используйте ленивое удаление или упорядоченную структуру. - Потерянный индекс запроса. При офлайн-обработке события сортируются, и без сохранённого индекса ответы вернутся не в том порядке.
- Плавающая точка в геометрии. Векторное произведение в целых числах точное; переход на
floatдаёт ложные «почти пересечения». - Свип там, где хватит массива. Если координаты до и все операции известны заранее, разностный массив проще и быстрее: без сортировки.
Как распознать задачу на собеседовании
Признаки, что поможет заметающая прямая:
- объекты — интервалы, отрезки или прямоугольники, а вопрос про одновременность: «в какой момент больше всего», «сколько активно в точке», «есть ли пересечение»;
- ответ меняется только в концах объектов, а координаты большие;
- двумерная задача, которую можно превратить в серию одномерных: прямая идёт по , а внутри неё решается задача по ;
- есть набор запросов, известный заранее, — кандидат на офлайн-обработку.
Хорошая подача на интервью: назовите наивное решение, сформулируйте наблюдение «между концами ничего не меняется», перечислите события и их порядок при равных координатах, затем скажите, какая структура держит состояние и сколько стоит одна операция. Сложность после этого выводится сама. Если задача про переговорки или слияние, сначала проверьте, не хватит ли подхода из задач на интервалы — он короче.
Перед собеседованием полезно решить: Meeting Rooms II (253), Car Pooling (1094), Number of Flowers in Full Bloom (2251), The Skyline Problem (218), Rectangle Area II (850). Для тренировки самой сортировки событий подойдут и разборы из статьи про жадные алгоритмы.
Что запомнить
- Sweep line — это события, отсортированные по координате, и состояние, которое обновляется на каждом событии.
- Между соседними событиями ничего не меняется, поэтому достаточно остановок вместо перебора всей оси.
- Порядок событий с одинаковой координатой определяется тем, считается ли касание пересечением. Для
[l, r)закрытия первыми, для[l, r]— открытия. - Тип состояния определяет задачу: счётчик — одновременность, куча — максимум высоты, Фенвик — подсчёт в диапазоне, дерево поиска — соседи по .
- Запросы, известные заранее, можно сделать событиями и ответить на все за один проход.