Module: 扫描线方式


Problem

1 /4


最低覆盖率

Theory Click to read/hide

Problem

一组具有整数坐标的线段 \([L_i, R_i]\) 在一条线上给出。在给定的集合中，选择一个完全覆盖段 \([0, M]\), (M —自然数）包含最小的段数。
 
输入
第一行包含常量M (\(1<=M<=5000\))。随后的每一行都包含一对数字 Li 和 Ri (\(|L_i|,|R_i| < 50000\))，指定线段左右两端的坐标。该列表以一对零结尾。段总数不超过100,000。
 
输出
在输出文件的第一行打印覆盖段 \([0; M]\) 所需的最少段数。接下来，输出覆盖子集的列表，按段左端的坐标升序排序。段列表以与输入相同的格式输出。尾随的两个零不是必需的。如果段 \([0; M]\) 是段的原始集合\([L_i, R_i] \)< /span> 是不可能的，应该输出一个短语“No solution”。

 

例子
<头> <日># <正文>

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!

输入 输出
1
1
-1 0
-5 -3
2 5
0 0
 无解
2
1
-1 0
0 1
0 0
 1
0 1