2376:Cleaning Shifts

keyword

greedy　C++

概要

N(<25000)個の区間が与えられ、1からT(<10^6)を被覆するのに必要な最小の個数を求める問題。
区間スケジューリング問題によく似た何か。今選べる開始時刻を持った区間の内、終了時刻が最も遅いものを選べば良い。開始時刻でソートしておけば計算量を落とせる。

int main(){
    static ll ranges[25002];
    int i, j, n, t, from, to, ans=0;
    ll mask = (1<<30)-1;
    scanf("%d%d",&n,&t);

    REP(i,n){
        scanf("%d%d",&from, &to);
        ranges[i] = ((ll)from<<30) + to;
    }
    sort(ranges,ranges+n);

    from = 1;
    to = 0;
    i = 0;
    bool updated;
    while(1){
        updated = false;
        for(;i<n && (int)(ranges[i]>>30) <= from;i++){
            to = max(to,(int)(ranges[i]&mask));
            updated = true;
        }
        ans++;
        if(to >= t){
            printf("%d\n",ans);
            break;
        }
        if(i==n || !updated){
            printf("-1\n");
            break;
        }
        from = to + 1;
    }

    return 0;
}