---
title: "Заметающая прямая: отрезки в события, сортировка и счётчик"
url: https://algopath.pro/ru/blog/zametayushchaya-pryamaya
language: ru
summary: "Начало это плюс один, конец минус один, и один проход по отсортированным событиям. Разбор на примере, порядок при равных координатах, код на Python, Meeting Rooms II и Skyline."
updated: 2026-11-21
---

# Заметающая прямая: отрезки в события, сортировка и счётчик

**Короткий ответ.** Заметающая прямая превращает отрезки в события. Начало отрезка это плюс один, конец это минус один. Сортируем события по координате и идём слева направо со счётчиком. Счётчик в любой момент равен числу отрезков, накрывающих точку. Время O(n log n). Ниже сигналы в условии, код на Python, разбор и порядок при равных координатах.

 

## Что такое заметающая прямая?

 

Представьте вертикальную линию, которая едет по оси слева направо. Она проходит через начала и концы отрезков. В каждой точке мы знаем, сколько отрезков сейчас под линией.

 

Отрезков много, но интересных точек ровно 2n: начала и концы. Между ними ничего не меняется. Поэтому смотрим только на события.

 

Название пришло из геометрии. Английский термин sweep line.

 

Тот же приём называют методом событий. Суть в замене непрерывной оси на конечный список точек, где что-то меняется.

 

## Как заметающая прямая работает по шагам?

 

- Для каждого отрезка создаём два события: начало с +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) из-за сортировки. Отдельно назовите порядок при равенстве.

 

Потом сравните с массивом разностей и скажите, когда какой брать. Это показывает, что вы видите два приёма, а не один.

 

Отработать узнавание приёма можно на странице [линия развёртки](/ru/patterns/sweep-line). Соседний приём разобран на странице [массив разностей](/ru/patterns/difference-array).

 

## Вопросы и ответы

 

### Чем заметающая прямая отличается от массива разностей?

 

Идея одна: дельты по координатам. Массив разностей хранит их в массиве и требует маленьких координат. Заметающая прямая хранит их в отсортированном списке и работает с любыми.

 

### Как найти точку, где накрытие максимально?

 

Вторая функция выше. Запоминаете координату события, на котором счётчик впервые достиг максимума.

 

### Работает ли приём в двух измерениях?

 

Да, для площади объединения прямоугольников. Заметаем по x, а по y держим дерево отрезков или отсортированный список. Это уже сложная задача.

 

### Где приём встречается в реальных системах?

 

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