Метод сканирующей прямой для максимального перекрытия
Подсчитывайте одновременные интервалы по событиям
«Метод сканирующей прямой для максимального перекрытия» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Задача о максимальном пересечении
Сколько интервалов покрывают один и тот же момент одновременно? Пиковое количество — это максимальное пересечение, самая загруженная точка на временной шкале. 📈
Думайте о событиях
Перестаньте думать о целых интервалах. Разделите каждый из них на два события: +1 в момент начала и -1 в момент окончания.
Составьте список событий
Для каждого интервала добавьте событие начала и событие окончания в один общий список. Каждое событие содержит позицию и дельту, равную плюс или минус единице.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))Отсортируйте события
Отсортируйте каждое событие по позиции, чтобы пройти временную шкалу слева направо и обработать изменения в правильном порядке.
events.sort()Выполните проход и подсчёт
Пройдите по отсортированным событиям, поддерживая текущий счётчик. Добавляйте каждую дельту по мере продвижения — счётчик показывает, сколько интервалов активно сейчас.
active = 0
for pos, delta in events:
active += deltaОтслеживайте максимум
После каждого обновления сравнивайте счётчик с лучшим результатом на данный момент. Наибольшее значение, которого когда-либо достигает счётчик, — это максимальное пересечение.
best = max(best, active)Приём с разрешением равенства
При одинаковых позициях порядок имеет значение. Если окончание в точке x должно освободить место до начала в точке x, располагайте окончания раньше начал в одной и той же точке.
Закодируйте дельты для правильной сортировки
Удобный способ разрешить равенства — выбрать дельты так, чтобы сортировка кортежей сделала это за вас. Размещайте дельту -1 перед дельтой +1 при совпадении позиций.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tieПочему это быстро
Вы создаёте 2n событий, один раз сортируете их и один раз выполняете проход. Весь метод работает за O(n log n), поскольку основное время занимает единственная сортировка.
Где это встречается
Максимальное пересечение помогает решать классические задачи: например, находить минимальное число комнат для совещаний или максимальное количество одновременных пользователей на сервере.
Не ограничивайтесь подсчётом
Тот же проход легко расширить: можно отслеживать общую покрытую длину или находить каждую позицию, где меняется количество, — всё за один линейный проход.
Быстрая проверка
Вы выполняете проход по событиям, чтобы найти максимальное пересечение.
Итоги
Преобразуйте интервалы в события +1 для начала и -1 для окончания, отсортируйте их и выполняйте проход со счётчиком, чтобы найти максимум. При равенстве обрабатывайте окончания раньше начал. 🚀
Часто задаваемые вопросы
Урок «Метод сканирующей прямой для максимального перекрытия» бесплатный?
Да — полный текст урока «Метод сканирующей прямой для максимального перекрытия» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Метод сканирующей прямой для максимального перекрытия»?
Подсчитывайте одновременные интервалы по событиям Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Метод сканирующей прямой для максимального перекрытия»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Сортировка интервалов по началу
- Слияние пересекающихся интервалов
- Метод сканирующей прямой для максимального перекрытия
- Минимальное число удалений без перекрытий