Выбор ответа Middle Интервалы обновлено
Минимум удалений
Вопрос
Сколько минимум интервалов удалить, чтобы оставшиеся не пересекались? По какому признаку сортировать для жадного решения?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: По концу: оставлять тот, что кончается раньше. Ранний конец оставляет больше места для следующих интервалов: это классическая жадность «выбор заявок».
Варианты ответа
- По концу: оставлять тот, что кончается раньшеправильный ответ
- По началу: оставлять тот, что начинается раньше
- По длине: оставлять самые короткие интервалы
- По середине: оставлять с самым ранним центром
Разбор
Ранний конец оставляет больше места для следующих интервалов: это классическая жадность «выбор заявок». Ответ = n минус число выбранных. O(n log n).
- Сортировка по началу без доп. логики может выбрать длинный ранний интервал, который перекроет много коротких.
- По длине: короткий интервал может пересекать два непересекающихся длинных.
- Середина не даёт корректного жадного критерия.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.