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