Модуль: Метод сканирующей прямой (scanline)


Задача

1 /4


Минимальное покрытие

Теория Нажмите, чтобы прочитать/скрыть

Задача

На прямой задано некоторое множество отрезков с целочисленными координатами концов \([L_i, R_i]\). Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок \([0, M]\), (M — натуральное число), содержащее наименьшее число отрезков.
 
Входные данные
В первой строке указана константа M (\(1<=M<=5000\)). В каждой последующей строке записана пара чисел Li и Ri (\(|L_i|,|R_i| < 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.
 
Выходные данные
В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка \([0; M]\). Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка \([0; M]\) исходным множеством отрезков \([L_i, R_i]\) невозможно, то следует вывести единственную фразу “No solution”.

 

Примеры
№ Входные данные Выходные данные
1
1
-1 0
-5 -3
2 5
0 0
 No solution
2
1
-1 0
0 1
0 0
 1
0 1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6413
Python2
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!