← вернуться к уроку · Практика: Жадные идеи и их ловушки
Проколоть все отрезки
5000 мс · 256 МБ · всё или ничего
На прямой нарисовано отрезков. Нужно отметить несколько точек так, чтобы на каждом отрезке оказалась хотя бы одна отмеченная точка. Точка на конце отрезка считается принадлежащей ему.
Какое наименьшее число точек нужно отметить?
Формат ввода
В первой строке число от до . Во второй — чисел: пары и подряд, .
Формат вывода
Одно число.
Примеры
ввод
3 1 5 4 7 6 10
вывод
2
Примечание
Отрезок, который заканчивается раньше всех, придётся проколоть — и выгоднее всего сделать это в самом его конце.
Войдите, чтобы отправлять решения.