OpenJudge

2:线段覆盖(cover)

总时间限制:
1000ms
内存限制:
262144kB
描述

给定x轴上的n0)条线段。每个线段由它的两个端点aibi确定,i=12n。这些坐标都是区间(-999999)的整数。有些线段之间会互相交叠或覆盖。请你写一个程序,从给出的线段中去掉尽量少的线段,使得剩下的线段两两之间没有内部公共点。所谓内部公共点是枕一个点同时属于两条线段且至少在其中一条线段的内部(即除去端点的部分)。

输入
第一行一个整数n;
接下来n行,每行有两个空格隔开的整数ai,bi,表示第i条线段的两个端点的坐标。
输出
第一行一个整数表示最多剩下的线段数。接下来的每行两个数表示一条剩下的线段,注意按坐标升序排列。如果有多个解,只输出其中一个解。
样例输入
3
6 3
1 3
2 5
样例输出
2
1 3
3 6
提示
贪心
全局题号
6306
添加于
2013-09-21
提交次数
9
尝试人数
4
通过人数
4