НачалоПодразделы
| 648. Космическая станция |
Другие разделы
Дата и время
20/12/2024 12:43:35
Занятие 7
A. Спрятанный текст B. Сдача C. Космическая станция D. Задача о расписании E. Канатная дорога F. Отрезки G. Advertisement
F. Отрезки
Динамическое программирование и запоминающие функцииЖадные алгоритмы
Олимпиадные задачи на русском языке
| 24/10/2007 | Занятие 7 (F) |
| 19/11/2011 | Занятие 6 (E) |
| 30/04/2014 | Занятие 23 (D) |
| 14/04/2015 | Занятие 21 (B) |
| 10/07/2017 | Лето 2017 (1 курс) - 6 (A) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На прямой линии определенным образом расположено `N` отрезков (`N` < 500). Из них нужно выбрать максимальное количество непересекающихся, т.е. не имеющих ни одной общей точки. Считать, что координаты концов всех отрезков являются целыми числами.
Требуется написать программу, которая определяет максимальное число отрезков и выводит координаты их концов (в случае, если решение не единственно, можно выдать любое).
В первой строке входного файла задано целое число `N`. В каждой из последующих `N` строк – пара целых чисел, задающих левый и правый концы отрезка.
Выходной файл в первой строке содержит найденное количество отрезков, а затем список выбранных отрезков. Описание каждого отрезка должно располагаться на отдельной строке в виде пары чисел, задающих левый и правый концы отрезка.
Пример ввода
3 -1 3 4 6 3 5
Пример вывода
2 -1 3 4 6
