Заметающая прямая: отрезки в события, сортировка и счётчик
Elman Huseynov · 2026-11-21
Короткий ответ. Заметающая прямая превращает отрезки в события. Начало отрезка это плюс один, конец это минус один. Сортируем события по координате и идём слева направо со счётчиком. Счётчик в любой момент равен числу отрезков, накрывающих точку. Время O(n log n). Ниже сигналы в условии, код на Python, разбор и порядок при равных координатах.
Что такое заметающая прямая?
Представьте вертикальную линию, которая едет по оси слева направо. Она проходит через начала и концы отрезков. В каждой точке мы знаем, сколько отрезков сейчас под линией.
Отрезков много, но интересных точек ровно 2n: начала и концы. Между ними ничего не меняется. Поэтому смотрим только на события.
Название пришло из геометрии. Английский термин sweep line.
Тот же приём называют методом событий. Суть в замене непрерывной оси на конечный список точек, где что-то меняется.
maxOverlap([[1, 4], [2, 5], [7, 9], [3, 6], [5, 8]])| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|
| [1,4] | ■ | ■ | ■ | ■ | |||||
| [2,5] | ■ | ■ | ■ | ■ | |||||
| [7,9] | ■ | ■ | ■ | ||||||
| [3,6] | ■ | ■ | ■ | ■ | |||||
| [5,8] | ■ | ■ | ■ | ■ |
Сколько интервалов открыто в самый загруженный момент? Каждый интервал это строка на шкале.
Страница паттерна: когда его применять и шаблон на шести языках
Как заметающая прямая работает по шагам?
- Для каждого отрезка создаём два события: начало с +1 и конец с -1.
- Сортируем события по координате. При равной координате сначала -1, если концы открытые.
- Идём по событиям и прибавляем к счётчику.
- После каждого события счётчик это число отрезков в этой точке. Запоминаем максимум или нужную точку.
Порядок при равенстве это единственное тонкое место. Одна встреча кончается в 10, другая начинается в 10. Они не пересекаются. Значит минус идёт первым.
Как это выглядит на примере?
Встречи [0, 30], [5, 10], [15, 20]. События по порядку: 0 плюс, 5 плюс, 10 минус, 15 плюс, 20 минус, 30 минус. Счётчик после каждого: 1, 2, 1, 2, 1, 0. Максимум 2, нужно две переговорки.
Добавим встречу [10, 12]. События (10, -1) и (10, +1) стоят рядом. Минус первым: счётчик 1, потом 2. Ответ остаётся 2. Плюс первым дал бы 3, а это неверно.
Как написать заметающую прямую на Python?
def min_meeting_rooms(intervals):
events = []
for s, e in intervals:
events.append((s, 1))
events.append((e, -1))
events.sort() # при равной координате -1 раньше +1
rooms = best = 0
for _, delta in events:
rooms += delta
best = max(best, rooms)
return best
def max_overlap_point(intervals):
events = sorted([(s, 1) for s, e in intervals] + [(e, -1) for s, e in intervals])
count = best = 0
point = None
for x, delta in events:
count += delta
if count > best:
best, point = count, x
return point, best
def car_pooling(trips, capacity):
delta = {}
for people, start, end in trips:
delta[start] = delta.get(start, 0) + people
delta[end] = delta.get(end, 0) - people
load = 0
for x in sorted(delta):
load += delta[x]
if load > capacity:
return False
return True
Кортежи (координата, дельта) сортируются сами: при равной координате -1 меньше +1. Это и даёт нужный порядок.
Чем заметающая прямая отличается от соседних приёмов?
| Приём | Вопрос | Время | Когда брать |
|---|---|---|---|
| Заметающая прямая | Сколько отрезков в точке, где максимум | O(n log n) | Координаты любые, в том числе большие |
| Массив разностей | То же самое | O(n + max) | Координаты маленькие целые |
| Слияние интервалов | Объединить пересекающиеся | O(n log n) | Нужны сами отрезки, а не счёт |
| Куча концов | Число переговорок | O(n log n) | Нужно знать, какая комната освободилась |
Как решить Meeting Rooms II?
Минимальное число переговорок равно максимальному числу встреч в один момент. Это первая функция выше. Куча концов даёт тот же ответ, но события короче и понятнее.
Как решить The Skyline Problem?
Здания это отрезки с высотой. Заметаем по x. При начале здания добавляем высоту в структуру, при конце убираем. После каждого события смотрим текущую максимальную высоту. Она изменилась, записываем точку.
Структура это куча с ленивым удалением. Порядок при равном x здесь свой: сначала высокие начала, потом низкие концы.
Как решить Car Pooling?
Поездки заданы как число пассажиров, точка посадки и точка высадки. Вместимость машины capacity. Для каждой поездки создаём событие плюс пассажиры в точке посадки и минус в точке высадки. Идём по отсортированным точкам и считаем загрузку. Превысила вместимость, ответ нет.
Это третья функция выше. Дельты здесь не единицы, а число людей. Приём не меняется.
По каким словам в задаче узнать приём?
- «Сколько отрезков накрывают точку», «максимум одновременных».
- «Хватит ли вместимости» при посадках и высадках.
- «Минимальное число комнат, платформ, серверов».
- «Контур зданий», «объединение прямоугольников».
На каких ошибках ломается решение?
- Плюс раньше минуса при равной координате. Касающиеся отрезки считаются пересекающимися.
- Забывают, что для закрытых концов порядок обратный.
- Считают максимум до применения события, а не после.
- Берут массив разностей на координатах до миллиарда и получают гигантский массив.
Как объяснить приём на собеседовании?
Скажите: превращаю отрезки в события плюс один и минус один. Сортирую, иду со счётчиком. Назовите O(n log n) из-за сортировки. Отдельно назовите порядок при равенстве.
Потом сравните с массивом разностей и скажите, когда какой брать. Это показывает, что вы видите два приёма, а не один.
Отработать узнавание приёма можно на странице линия развёртки. Соседний приём разобран на странице массив разностей.
Вопросы и ответы
Чем заметающая прямая отличается от массива разностей?
Идея одна: дельты по координатам. Массив разностей хранит их в массиве и требует маленьких координат. Заметающая прямая хранит их в отсортированном списке и работает с любыми.
Как найти точку, где накрытие максимально?
Вторая функция выше. Запоминаете координату события, на котором счётчик впервые достиг максимума.
Работает ли приём в двух измерениях?
Да, для площади объединения прямоугольников. Заметаем по x, а по y держим дерево отрезков или отсортированный список. Это уже сложная задача.
Где приём встречается в реальных системах?
В планировании нагрузки: сколько серверов занято в каждый момент. В календарях при подсчёте конфликтов. В графике при отрисовке перекрытий.