线段覆盖问题nbsp;算法及程序

线段覆盖问题nbsp;算法及程序
覆盖（cover.cpp/c）题目描述:已知数轴上0amp;lt;Namp;lt;10000条线段.每条线段按照端点Ai和Bi（Aiamp;lt;amp;gt;Bi,i=1..N）定义.端点坐标在（-999,999）内,坐标为整数.有些线段可能相交.编程实现删除最少数目的线段,使得余下的任意两条线段不相交.输入：第一行为一整数N.接下来有N行,每行包含两个整数nbsp;(Ainbsp;和nbsp;Bi),nbsp;用空格隔开.输出：整数p,即删除后余下的线段数.样例输入：36nbsp;31nbsp;32nbsp;5样例输出：2

我的算法:我采用贪心的算法,nbsp;按照左端点排序,nbsp;建立一个以线段右端点为关键字的大根堆.依次尝试插入线段,nbsp;对于当前的一个线段,nbsp;如果能够覆盖,显然我们选择覆盖,nbsp;而如果不能覆盖,nbsp;我们进行一下讨论.首先我们需要知道(1)nbsp;如果线段发生相交,nbsp;那么只可能是两条线段相交:理由:nbsp;对于前面的所有线段,贪心法保证,也显然,已经满足两两不相交了,nbsp;那么如果当前的线段,和另外两条线段相交,nbsp;则必然将一条线段包含,nbsp;而我们按照线段左端点排序,nbsp;按次序尝试覆盖,nbsp;因此这种情况是不存在的.那么我们假设当前的线段是nbsp;[L0,nbsp;R0]nbsp;发生相交的线段是nbsp;[L1,nbsp;R1]即有nbsp;L0nbsp;amp;gt;=nbsp;L1nbsp;R0nbsp;amp;lt;=nbsp;R1nbsp;这两条线段是不能共存的.显然,我们要从中留下一个而舍去一个,nbsp;舍去哪个呢?nbsp;就应该选择右端点小的那个!nbsp;为什么?nbsp;因为右端点越靠左,对后面的线段的覆盖产生的影响(就是发生覆盖的机会)就越小!nbsp;很直观的,nbsp;我们可以知道这种贪心法的正确性.问题就解决了时间复杂度nbsp;O(Nnbsp;lognbsp;N)我写的代码:#includeamp;lt;cstdioamp;gt;#includeamp;lt;vectoramp;gt;#includeamp;lt;queueamp;gt;#includeamp;lt;algorithmamp;gt;usingnbsp;namespacenbsp;std;constnbsp;intnbsp;maxnnbsp;=nbsp;10010;structnbsp;eventnbsp;{nbsp;intnbsp;l,nbsp;r;}e[maxn];structnbsp;__Compnbsp;{nbsp;inlinenbsp;intnbsp;operator()nbsp;(constnbsp;eventnbsp;amp;a,nbsp;constnbsp;eventnbsp;amp;b)nbsp;constnbsp;{nbsp;nbsp;returnnbsp;a.rnbsp;amp;lt;nbsp;b.r;nbsp;}};priority_queueamp;lt;event,nbsp;vectoramp;lt;eventamp;gt;,nbsp;__Compamp;gt;nbsp;hp;intnbsp;n,nbsp;l,nbsp;r;inlineintnbsp;comp(constnbsp;eventnbsp;amp;a,nbsp;constnbsp;eventnbsp;amp;b)nbsp;{returnnbsp;a.lnbsp;amp;lt;nbsp;b.l;}intnbsp;main()nbsp;{nbsp;scanf(“%d“,nbsp;amp;n);nbsp;fornbsp;(intnbsp;i=0;iamp;lt;n;++i)nbsp;{nbsp;nbsp;scanf(“%dnbsp;%d“,nbsp;amp;l,nbsp;amp;r);nbsp;e[i]nbsp;=nbsp;(event){lamp;lt;?r,nbsp;lamp;gt;?r};nbsp;}sort(e,nbsp;e+n,nbsp;comp);nbsp;fornbsp;(intnbsp;i=0;iamp;lt;n;++i)nbsp;{nbsp;nbsp;ifnbsp;(!i)nbsp;{hp.push(e[0]);nbsp;continue;}nbsp;nbsp;ifnbsp;(e[i].lnbsp;amp;gt;=nbsp;hp.top().r)nbsp;hp.push(e[i]);nbsp;nbsp;nbsp;elsenbsp;nbsp;nbsp;ifnbsp;(hp.top().rnbsp;amp;gt;nbsp;e[i].r)nbsp;{nbsp;nbsp;nbsp;nbsp;hp.pop();nbsp;hp.push(e[i]);nbsp;nbsp;nbsp;}nbsp;}nbsp;printf(“%d “,nbsp;hp.size());scanf(“%*s“);} 查看原帖