UVA 10020 Minimal coverage ( 水題區間覆蓋 )

UVa Online Judge
很單純的區間覆蓋問題。注意覆蓋的是端點而非區間。

#include <bits/stdc++.h>
using namespace std;
const int MAXLR = 5e4 + 4;
const int MAXM = 5000 + 3;
const int MAXP = 1e6 + 5;

int m;
typedef pair<int, int> pii;
int n;
pii p[MAXP];

void solve(){
    sort( p, p + n );
    n = unique( p, p + n ) - p;
    int best_idx, pos = 0, cnt = 0;
    vector<int> chosen;
    int rb = 0;
    while( pos < m ){
        best_idx = -1;
        while( rb < n && p[ rb ].first <= pos ){
            if( best_idx < 0 || p[ rb ].second > p[ best_idx ].second )
                best_idx = rb;
            ++rb;
        }
        if( best_idx < 0 ) break;
        ++cnt;
        pos = p[ best_idx ].second;
        chosen.push_back( best_idx );
    }
    if( pos < m ){ puts("0"); return; }
    printf("%d\n", cnt);
    assert( cnt == chosen.size() );
    for(int i = 0; i < cnt; ++i)
        printf("%d %d\n", p[ chosen[ i ] ].first, p[ chosen[ i ] ].second);
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d", &m);
        n = 0;
        while( true ){
            int a, b; scanf("%d%d", &a, &b);
            if( a == 0 && b == 0 ) break;
            p[ n++ ] = pii( a, b );
        }
        solve();
        if( T ) puts("");
    }
    return 0;
}