Картина Сакурако#372

Картина Сакурако (Розбір)

Автор задачі:

Олександр Тимкович

Задачу підготував:

Богдан Фейса

Розбір написав:

Павло Ціцей

Рішення цієї задачі полягає в тому, щоб відсортувати всі відрізки в порядку зростання початкової точки і намагатися жадібно знайти відповідь. Отже, з першого сегмента ми беремо всі точки, які він займає. Для другого — всі точки, які не входять в перший сегмент (тобто деякий суфікс його), у третьому — всі, які не входять в перший або другий, і так далі. У результаті ми беремо максимальну кількість точок, і ми візьмемо деякий (можливо, порожній) суфікс кожного сегмента.