Мінімальне покриття#4426
Серед заданої множини відрізків прямої з цілими координатами кінців L_i, R_i необхідно вибрати підмножину найменшої потужності, яка повністю покриває відрізок , де — ціле додатне число.
У першому рядку зазначено ціле число (1 \leq M \leq 5000). У наступних рядках перелічені пари цілих чисел L_i та R_i (|L_i|, |R_i| \leq 50000), кожна пара записується з нового рядка, числа в парах відокремлені одним або кількома пропусками. Список завершується парою нулів. Список містить не більше пар чисел, враховуючи пару нулів.
У першому рядку виведіть мінімальну кількість відрізків із заданої множини, необхідну для покриття відрізка . Далі виведіть список покриваючої підмножини, відсортований за зростанням координат лівих кінців відрізків. Список відрізків виводиться у такому ж форматі, як і у вхідних даних, завершальну пару нулів виводити не потрібно.
Якщо покрити відрізок заданою множиною відрізків [L_i, R_i] неможливо, виведіть єдину фразу No solution.
Приклад 1