[UV] 10020 Minimal Converge.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

struct line{
    int L;
    int R;
}a[100001];

bool cmp(line a,line b){
    if(a.L == b.L) return a.R < b.R;
    return a.L < b.L;
}
int main()
{
    int T,M;
    scanf("%d",&T);
    while (T--){
        scanf("%d",&M);
        int i,j,n=0;
        while (scanf("%d%d", &a[n].L,&a[n].R)){
            if (!a[n].L && !a[n].R) break;
            n++;
        }
        sort(a,a+n,cmp);

        int ans=0,left=0,right=0,Max=0,Max_index; //left是存a_index,right是存max
        int List[100001],l_index=0;
        bool Ans=1;

        while (Max<M){   //不斷靠近M
            right=Max;
            for(i=left;a[i].L<=right && i<n;i++){ /*a[i].L不能>right，不然範圍會沒有覆蓋*/
                if (Max<a[i].R){   //在沒有超過範圍的情況下，不斷找最靠近右邊的R
                    Max=a[i].R;
                    Max_index=i;
                }
            }
            if (Max==right) {Ans=0; break;}  //找不到的情況
            List[l_index++]=Max_index;       //將找到的點放入List
            ans++;
            left = i;
        }

        if(Ans){
            printf("%d\n",ans);
            for(i=0;i<l_index;i++)
                printf("%d %d\n",a[List[i]].L,a[List[i]].R);
        }
        else printf("0\n");

        if(T) printf("\n");

    }
    return 0;
}