Минимальное число удалений без перекрытий
Жадное планирование с сохранением раннего конца
«Минимальное число удалений без перекрытий» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Цель удаления
У вас есть пересекающиеся интервалы, и вы хотите выполнить как можно меньше удалений, чтобы пересечений больше не осталось. Сохраните как можно больше интервалов. ✂️
Измените формулировку задачи
Удалить минимальное количество интервалов — то же самое, что сохранить максимальное количество непересекающихся интервалов. Решите задачу о сохранении, а затем вычислите количество удалений как n минус количество сохранённых интервалов.
Это выбор действий
Сохранение максимального количества непересекающихся интервалов — это классическая задача о выборе действий в другой формулировке. Одна и та же жадная идея решает обе задачи.
Сортируйте по окончанию
Здесь правильный порядок определяется временем окончания, а не началом. Раннее окончание быстрее освобождает временную шкалу для следующего интервала, который вы сможете сохранить.
intervals.sort(key=lambda x: x[1])Жадный выбор
Всегда сохраняйте совместимый интервал, который заканчивается раньше всех. Так для остальных интервалов остаётся максимум места.
Отслеживайте окончание последнего сохранённого интервала
Храните окончание последнего сохранённого интервала. Следующий интервал совместим только в том случае, если его начало находится на этой границе или правее неё.
if start >= last_end:
last_end = endПодсчитайте удаления
Если интервал начинается раньше, чем last_end, он конфликтует, поэтому отбрасывайте его и увеличивайте счётчик удалений на единицу. В противном случае сохраняйте его.
else:
removed += 1Почему выигрывает самое раннее окончание
Это доказывает аргумент об обмене: замена любого сохранённого интервала на совместимый интервал с самым ранним окончанием никогда не уменьшает количество интервалов, которые можно сохранить.
Обработайте случай соприкосновения
Определите, считаются ли [1, 2] и [2, 3] пересекающимися. Если общий конец интервала разрешён, используйте start >= last_end как условие проверки.
Полный жадный алгоритм
Отсортируйте по окончанию, выполните один проход и подсчитайте конфликты. Общая сложность — O(n log n) из-за сортировки и одного линейного прохода.
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1Знакомая структура
Этот шаблон позволяет запланировать максимум совещаний в одной комнате или разместить максимум заданий на одном компьютере. Распознавайте его, когда конфликты нужно минимизировать.
Быстрая проверка
Вы жадно сохраняете непересекающиеся интервалы.
Итоги
Минимальное количество удалений равно n минус максимальное количество интервалов, которые можно сохранить. Сортируйте по окончанию, жадно сохраняйте совместимые интервалы с самым ранним окончанием и подсчитывайте остальные. 🚀
Часто задаваемые вопросы
Урок «Минимальное число удалений без перекрытий» бесплатный?
Да — полный текст урока «Минимальное число удалений без перекрытий» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Минимальное число удалений без перекрытий»?
Жадное планирование с сохранением раннего конца Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Минимальное число удалений без перекрытий»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Сортировка интервалов по началу
- Слияние пересекающихся интервалов
- Метод сканирующей прямой для максимального перекрытия
- Минимальное число удалений без перекрытий