uva 10020- Minimal coverage （贪心思想 简单区间覆盖）

题目大意：给出一个范围M,然后给出若干的区间，以0 0 终止， 要求用最少的区间将0 ~M 覆盖，输出最少个数以及方案。

解题思路：典型的区间覆盖问题，算法竞赛入门经典P154上有讲。

/*author: charkj_z */
/*time: 0.108s */
/*rank: 674 */
/*为什么不把没用的地方去掉？ 因为去掉了我觉得不像我能写出来的*/
/*Ac code : */

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int maxn=100010; struct qujian { int x; int y; }s[maxn]; bool cmp(const qujian a,const qujian b) { if(a.x!=b.x) return a.x
      
       order) break; max=0; int k; for(int k=0;k
       
        begin) /*对于开始和中间每一步，这个判断都是适合的 若当前最靠左的区间左端点已经超出所覆盖区间右端点，无法继续覆盖*/ { k--; printf("k = %d\n",k); break; } if(s[i+k].y>max) /*在上面的if的前提下，即可以覆盖的前提下，找出可用区间中区间最靠右的区间 更新最当前最大值，同时用id记录下该区间坐标*/ { max=s[i+k].y; id=i+k; } } if(k>0)/*直接跳过在上面循环中去掉的不符合的区间*/ i+=k; if(max
        
         =order)/*边界条件，达到此条件时覆盖成功，跳出循环*/ break; } /*输出格式不解释*/ if(max>=order) { printf("%d\n",cnt); for(int i=0;i