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.xorder)
                break;
            max=0;
            int k;
            for(int k=0;kbegin)
                /*對於開始和中間每一步，這個判斷都是適合的
                若當前最靠左的區間左端點已經超出所覆蓋區間右端點，無法繼續覆蓋*/
                {
                    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