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