Module: Scanline method


Problem

1 /4


Minimum coverage

Theory Click to read/hide

Problem

A certain set of segments with integer coordinates of ends \([L_i, R_i]\) is given on a line. Among the given set, choose a subset of segments that completely covers the segment \([0, M]\), (M — natural number) containing the smallest number of segments.
 
Input
The first line contains the constant M (\(1<=M<=5000\)). Each subsequent line contains a pair of numbers Li and Ri (\(|L_i|,|R_i| < 50000\)), which specifies the coordinates of the left and right ends of the segments. The list ends with a pair of zeros. The total number of segments does not exceed 100,000.
 
Output
In the first line of the output file print the minimum number of segments required to cover the segment \([0; M]\). Next, output a list of the covering subset, sorted in ascending order by the coordinates of the left ends of the segments. The list of segments is output in the same format as in the input. The trailing two zeros are not required. If the segment \([0; M]\) is the original set of segments \([L_i, R_i]\)< /span> is not possible, a single phrase “No solution” should be output.

 

Examples
# Input Output
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
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!