ACM UVA-10020

這題是greedy。

首先以左端點排序所有線段,一開始邊界的左端為0,所以找所有線段的左端點小於等於0的,然後右端點是最長的,接著把右端點設成邊界的左端,接著又是解決同樣的子問題。

//ignore header files
struct line{
    int left,right;
    line(int a,int b){
        left = a;
        right = b;
    }
    bool operator<(const line & lvalue) const{
        return left<lvalue.left;
    }
};
int main(int argc, char const* argv[])
{
    int n;
    while(scanf("%d",&n) != EOF){
    for(int g = 0;g<n;g++){
        int m;
        scanf("%d",&m);
        int l,r;
        vector<line> v;
        while(scanf("%d %d",&l,&r) && !(l == 0 && r == 0)){
            v.push_back(line(l,r));
        }
        sort(v.begin(),v.end());
        int currentl = 0;
        int currentr = 0;
        vector<line> ans;
        for(size_t i = 0;i<v.size() ;i++){
            int u = -1;
            for(;i<v.size()&&v[i].left<= currentl;i++){
                if(v[i].right>currentr){
                    currentr = v[i].right;
                    u = i;
                }
            }
            if(u  == -1)
                break;
            ans.push_back(v[u]);
            if(currentr >= m)
                break;
            currentl = currentr;
            i--;
        }

        if(currentr<m){
            printf("0\n");
        }else{
            if(g>0)
                printf("\n");
            printf("%d\n",ans.size());
            for(size_t y = 0;y<ans.size();y++)
                printf("%d %d\n",ans[y].left,ans[y].right);
        }
    }
    }
    return 0;
}