Задача 2. "Минимальное покрытие". Городская олимпиада по информатике 2001/2002 г.

Олимпиады по информатике 2001/2002 г.

Задача 3. "Минимальное покрытие". 25 баллов

Среди заданного множества отрезков прямой с целочисленными координатами концов [L_i, R_i] необходимо выбрать подмножество, целиком покрывающее отрезок [0,M] (M - натуральное число) и содержащее наименьшее количество отрезков.

Ограничения: 1 Ј M Ј 10000; | Li |, | Ri | Ј 32000; i Ј 10000.

В первой строке входного файла INPUT.TXT указана константа M, во второй - количество отрезков N. В последующих N строках перечислены пары чисел L_i R_i, каждая пара с новой строки, числа в парах отделены друг от друга пробелами.

Программа должна формировать в первой строке выходного файла OUTPUT.TXT требуемое минимальное число отрезков из исходного множества, необходимое для покрытия отрезка [0,M]. Далее должен следовать список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входном файле INPUT.TXT.

Если покрытие отрезка [0,M] исходным множеством отрезков [L_i,R_i] невозможно, то файл OUTPUT.TXT должен содержать единственное число 0.

Пример INPUT.TXT: OUTPUT.TXT для примера:

8 3 -1 7 -2 9 6 8 1 -2 9

Ограничение времени: 10 сек на тест

Один из вариантов решения (на языке Паскаль)

Пример INPUT.TXT:	OUTPUT.TXT для примера:
`8 3 -1 7 -2 9 6 8`	`1 -2 9`