Sweep line: алгоритм заметающей прямой для интервалов, skyline и пересечений

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

13 мин чтенияалгоритмы · сортировка · интервалы · python

Коротко

ЧтоСуть
ИдеяДвигаем воображаемую прямую слева направо и реагируем только на события — точки изменений
СобытиеПара «координата + что произошло»: интервал открылся, закрылся, пришёл запрос
СостояниеТо, что знает прямая в текущей точке: счётчик, куча, дерево Фенвика, множество отрезков
СложностьO(nlog⁡n)O(n \log n) на сортировку событий плюс стоимость обновления состояния
Главная ловушкаПорядок событий с одинаковой координатой — он решает, касание это пересечение или нет
Где спрашиваютMeeting Rooms II, Skyline Problem, Number of Flowers in Full Bloom, Rectangle Area II

Если вы уже решали «минимальное число переговорок» через отсортированные начала и концы — вы уже пользовались заметающей прямой. Базовые задачи на отрезки (слияние, вставка, пересечение двух расписаний) разобраны в статье про задачи на интервалы, здесь повторять их не будем. Эта статья — про сам приём: как его обобщить, где он ломается и как с ним решаются задачи уровня Hard.

Интуиция: смотрим только на точки изменений

Представьте ось времени и на ней сотню встреч. Вопрос: сколько встреч идёт одновременно в самый загруженный момент?

Наивный способ — перебрать все моменты времени и для каждого посчитать покрывающие его встречи. Если время целое и лежит в пределах 10910^9, это безнадёжно. Даже если перебирать только концы встреч, получится O(n2)O(n^2): 2n2n точек, и для каждой проход по всем встречам.

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

  1. Превратить каждый объект в события — точки, где что-то меняется.
  2. Отсортировать события по координате.
  3. Пройти по ним один раз, поддерживая состояние «что сейчас пересекает прямую».

Вся разница между задачами — в том, что считать событием и какую структуру держать в качестве состояния. Для подсчёта хватает одного целого числа, для 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: «а когда именно пик нагрузки?».

Разберём первый пример по шагам:

СобытиеactivebestКомментарий
(0, +1)11началась встреча 0–30
(5, +1)22началась 5–10, пик
(10, -1)125–10 закончилась
(15, +1)22началась 15–20
(20, -1)12
(30, -1)02все закончились

Ответ 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, и это ровно разностный массив, в котором хранятся только ненулевые ячейки. Когда координаты маленькие, массив проще; когда до 10910^9 — сортируем события.

Порядок событий при равной координате

Это место, где ломается большинство решений. Сортировка по координате однозначна, пока координаты разные. Как только в одной точке встречаются начало и конец, результат зависит от того, что обработать первым.

ОтрезкиКасание — пересечение?Порядок в одной точкеЧто ответит [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]. Сколько цветов цветёт для каждого человека?

Наивно — O(n⋅m)O(n \cdot m). Свип даёт O((n+m)log⁡(n+m))O((n + m) \log(n + m)): добавляем запросы как третий тип событий. Когда прямая доходит до запроса, текущее значение счётчика и есть ответ.

Порядок в одной точке: цветок, распустившийся в момент 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]].

Сложность — O(nlog⁡n)O(n \log n): 2n2n событий, каждое здание один раз попадает в кучу и один раз из неё выходит. В Java и C++ вместо ленивой кучи часто берут TreeMap/multiset с честным удалением — асимптотика та же. Подробнее про кучу и её ловушки — в статье про очередь с приоритетом.

Пересечения отрезков

Здесь sweep line родом — из вычислительной геометрии. Классическая постановка: дано nn отрезков на плоскости, нужно найти их пересечения.

Базовая проверка двух отрезков

Сначала нужен примитив: пересекаются ли два конкретных отрезка. Он строится на знаке векторного произведения — повороте тройки точек:

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(n2)O(n^2), и для nn до нескольких тысяч этого достаточно.

Горизонтальные и вертикальные: точный подсчёт за O(n log n)

Частный случай, который реально дают на собеседованиях и олимпиадах: отрезки только горизонтальные и вертикальные, нужно посчитать число пересечений. Пересечений может быть Θ(n2)\Theta(n^2), но нам нужно только их количество.

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

  • левый конец горизонтали — добавить её yy;
  • вертикаль на абсциссе xx — посчитать, сколько активных yy попадает в [y1,y2][y_1, y_2];
  • правый конец горизонтали — убрать её yy.

Запрос «сколько чисел в диапазоне» при вставках и удалениях — это дерево Фенвика по сжатым координатам. Порядок в одной точке для закрытых отрезков: добавления → запросы → удаления, чтобы касания концами считались.

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

Сжатие координат нужно, потому что yy может быть до 10910^9, а дерево Фенвика индексируется плотно. Сортируем уникальные yy и заменяем значение его позицией — bisect_left. Для границ запроса y1 и y2, которых может не быть среди горизонталей, bisect_left и bisect_right дают ровно нужный полуинтервал индексов.

Итого O(nlog⁡n)O(n \log n): сортировка событий и по одной операции Фенвика на событие. Вместо Фенвика подойдёт и дерево отрезков, если нужно что-то кроме суммы.

Общий случай: Shamos–Hoey и Bentley–Ottmann

Для произвольных отрезков идея та же, но состояние хитрее: активные отрезки хранятся упорядоченными по yy в текущей точке прямой, обычно в сбалансированном дереве поиска.

  • Shamos–Hoey (1976) отвечает на вопрос «есть ли хоть одно пересечение» за O(nlog⁡n)O(n \log n). Ключевое наблюдение: если два отрезка пересекаются, то перед точкой пересечения они в какой-то момент становятся соседями в порядке по yy. Поэтому при вставке отрезка достаточно проверить его с двумя соседями, а при удалении — проверить друг с другом соседей удалённого.
  • Bentley–Ottmann (1979) находит все kk пересечений за O((n+k)log⁡n)O((n + k) \log n). Точки пересечения сами становятся событиями: в них два отрезка меняются местами в порядке по yy. События держат в очереди с приоритетом, потому что новые появляются по ходу свипа.

Писать Bentley–Ottmann на собеседовании никто не попросит: вырожденные случаи (вертикальные отрезки, три отрезка через одну точку, совпадающие концы) превращают его в сотни строк. Но знать идею полезно — это частый теоретический вопрос на позиции, связанные с геометрией, картами и CAD.

Площадь объединения прямоугольников

LeetCode 850, Rectangle Area II. Даны прямоугольники [x1, y1, x2, y2], нужно найти площадь их объединения, перекрытия считаются один раз.

Ведём вертикальную прямую по xx. Между двумя соседними событиями набор прямоугольников под прямой не меняется, значит, на этой полосе покрытая высота постоянна. Площадь полосы — ширина, умноженная на длину объединения yy-отрезков активных прямоугольников. А объединение отрезков — задача слияния интервалов из соседней статьи.

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, потом обновляем состояние. Перепутать — значит прибавить полосу с неправильным набором прямоугольников.

Сложность — O(n2log⁡n)O(n^2 \log n): на каждом из 2n2n событий сортируем до nn отрезков. В LeetCode n≤200n \le 200, этого хватает с запасом. Если nn до 10510^5, длину объединения поддерживают деревом отрезков по сжатым yy: каждый узел хранит, сколько прямоугольников покрывают его целиком, и длину покрытой части. Тогда общая сложность O(nlog⁡n)O(n \log n) — это классическая олимпиадная задача.

Сложность: сводка

ЗадачаСобытияСостояниеВремя
Максимум одновременныхначало, конецсчётчикO(nlog⁡n)O(n \log n)
Ответы для точек-запросовначало, запрос, конецсчётчикO((n+m)log⁡(n+m))O((n+m)\log(n+m))
Skylineлевый и правый крайкуча с ленивым удалениемO(nlog⁡n)O(n \log n)
Пересечения H/V-отрезковконцы горизонталей, вертикалидерево Фенвика по yyO(nlog⁡n)O(n \log n)
Есть ли пересечение (общий случай)концы отрезковдерево поиска по yyO(nlog⁡n)O(n \log n)
Площадь прямоугольниковлевый и правый крайсписок или дерево отрезковO(n2log⁡n)O(n^2 \log n) / O(nlog⁡n)O(n \log n)

Память во всех случаях O(n)O(n) на события и состояние.

Типичные ошибки

  • Не продуман порядок при равных координатах. Решение проходит примеры и падает на касаниях. Перед кодом выпишите для каждой пары типов событий, кто идёт первым, и почему.
  • Сортировка без компаратора в JavaScript. [[10, 1], [9, 1]].sort() сравнивает строки, и 10 окажется раньше 9.
  • Обновление состояния до подсчёта ответа. В задачах с площадью или длиной сначала учитываем отрезок между предыдущим и текущим событием, потом применяем событие.
  • Попытка удалять из heapq по значению. heap.remove(x) ломает инвариант кучи и стоит O(n)O(n). Используйте ленивое удаление или упорядоченную структуру.
  • Потерянный индекс запроса. При офлайн-обработке события сортируются, и без сохранённого индекса ответы вернутся не в том порядке.
  • Плавающая точка в геометрии. Векторное произведение в целых числах точное; переход на float даёт ложные «почти пересечения».
  • Свип там, где хватит массива. Если координаты до 10510^5 и все операции известны заранее, разностный массив проще и быстрее: O(n+C)O(n + C) без сортировки.

Как распознать задачу на собеседовании

Признаки, что поможет заметающая прямая:

  • объекты — интервалы, отрезки или прямоугольники, а вопрос про одновременность: «в какой момент больше всего», «сколько активно в точке», «есть ли пересечение»;
  • ответ меняется только в концах объектов, а координаты большие;
  • двумерная задача, которую можно превратить в серию одномерных: прямая идёт по xx, а внутри неё решается задача по yy;
  • есть набор запросов, известный заранее, — кандидат на офлайн-обработку.

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

Перед собеседованием полезно решить: Meeting Rooms II (253), Car Pooling (1094), Number of Flowers in Full Bloom (2251), The Skyline Problem (218), Rectangle Area II (850). Для тренировки самой сортировки событий подойдут и разборы из статьи про жадные алгоритмы.

Что запомнить

  • Sweep line — это события, отсортированные по координате, и состояние, которое обновляется на каждом событии.
  • Между соседними событиями ничего не меняется, поэтому достаточно O(n)O(n) остановок вместо перебора всей оси.
  • Порядок событий с одинаковой координатой определяется тем, считается ли касание пересечением. Для [l, r) закрытия первыми, для [l, r] — открытия.
  • Тип состояния определяет задачу: счётчик — одновременность, куча — максимум высоты, Фенвик — подсчёт в диапазоне, дерево поиска — соседи по yy.
  • Запросы, известные заранее, можно сделать событиями и ответить на все за один проход.

Потренироваться в спокойной обстановке

Все задачи