Мы используем необходимые куки для работы сайта (вход и язык). Если ты согласишься, мы также загрузим Google Analytics, чтобы видеть, какие страницы читают, и Google reCAPTCHA для защиты форм обратной связи и сообщений об ошибке от спама. Политика конфиденциальности

← Блог
Как готовиться

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

· 2026-11-21

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

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

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

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

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

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

Наибольшее число одновременно открытых интервалов
maxOverlap([[1, 4], [2, 5], [7, 9], [3, 6], [5, 8]])
шкала (по строке на интервал)
123456789
[1,4]■■■■
[2,5]■■■■
[7,9]■■■
[3,6]■■■■
[5,8]■■■■
events
пусто
active = 0best = 0

Сколько интервалов открыто в самый загруженный момент? Каждый интервал это строка на шкале.

Страница паттерна: когда его применять и шаблон на шести языках

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

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

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

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