Courses

Algoritmos

método de línea de exploración

Module: método de línea de exploración

Problem

1 /4

Cobertura mínima

Theory Click to read/hide

Problem

Un cierto conjunto de segmentos con coordenadas enteras de extremos \([L_i, R_i]\) se da en una línea. Entre el conjunto dado, elija un subconjunto de segmentos que cubra completamente el segmento \([0, M]\), (M — número natural) que contiene el menor número de segmentos.

Entrada

La primera línea contiene la constante M (\(1<=M<=5000\)). Cada línea subsiguiente contiene un par de números L_i y R_i (\(|L_i|,|R_i| < 50000\)), que especifica las coordenadas de los extremos izquierdo y derecho de los segmentos. La lista termina con un par de ceros. El número total de segmentos no supera los 100 000.

Salida

En la primera línea del archivo de salida, imprima el número mínimo de segmentos necesarios para cubrir el segmento \([0; M]\). A continuación, genere una lista del subconjunto de cobertura, ordenada en orden ascendente por las coordenadas de los extremos izquierdos de los segmentos. La lista de segmentos se emite en el mismo formato que en la entrada. Los dos ceros finales no son obligatorios. Si el segmento \([0; M]\) es el conjunto original de segmentos \([L_i, R_i] \)< /span> no es posible, debe salir una sola frase “Sin solución”.