Код Senior Интервалы обновлено
Минимум удалений интервалов
Условие
Сколько интервалов надо удалить, чтобы оставшиеся не пересекались? Касание границ пересечением не считается.
Примеры
eraseOverlap([[1, 2], [2, 3], [3, 4], [1, 3]]) // 1
eraseOverlap([[1, 2], [1, 2], [1, 2]]) // 2
eraseOverlap([[1, 2], [2, 3]]) // 0
Как подойти
Сортировка по концу - редкий, но важный случай: жадно берём тот, что освобождается раньше, оставляя максимум места остальным. Сортировка по началу здесь даёт неверный ответ на длинном интервале, накрывающем несколько коротких. Классическая задача о выборе заявок.
Подсказки: 2
- Максимум непересекающихся интервалов - жадный выбор по раннему концу.
- Сортировка по концу, а не по началу.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.