Ребятки, сегодня с 11-м классом разбирали очередную порцию задач на сортировку, обещала закинуть вам на "подумать" задание с недавней ЕГКР (смотри картинку)

⚡️Примерная идея такая:
Классическая жадная стратегия по отрезкам:
• Каждую заявку переводим в отрезок
не как (start, длина), а как (конец, начало) - чтобы удобно сортировать.

• Сортируем все заявки по правому концу
→ сначала рассматриваем те, которые заканчиваются раньше.

• Жадно выбираем непересекающиеся отрезки
берём первый (самый ранний по окончанию)
дальше добавляем только те, у которых
начало ≥ конец последнего выбранного
так набирается максимальное количество заявок

• Параллельно следим за концом последнего выбранного отрезка
→ это важно для второй части задачи

• В конце считаем хвост дороги
→ 10000 - конец последнего отрезка
→ и пытаемся сделать его минимальным, перебирая допустимые варианты

Итого: сначала максимизируем количество непересекающихся отрезков (как в классической задаче), а потом среди таких вариантов выбираем тот, где последний отрезок заканчивается как можно правее.

Попробуйте решить 💅

❤️ - я всё решил!!
🤯 - че за жесть вообще