POJ 2376 – Cleaning Shifts [区间贪心]

题目链接:http://poj.org/problem?id=2376

题意:给定n个区间,取最少数目的区间,覆盖1~t。

先根据区间起点排序,只需要一次扫描。初始起点为1,记录起点在1之前的最长区间,最大终点记为to。当起点大于1时,若起点大于to+1,不满足条件,否则将to+1设置为新的起点,重复上述步骤即可。

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

pair<int, int> v[25005];

int main()
{
    int n, t; scanf("%d%d", &n, &t);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &v[i].first, &v[i].second);
    sort(v, v + n);
    int from = 1, to = 0, cnt = 1;
    for(int i = 0; i < n; ++i){
        if(v[i].first > from){
            ++cnt;
            from = to + 1;
        }
        if(v[i].first <= from){
            to = max(to, v[i].second);
            if(to >= t) break;
        }
        else break;
    }
    printf("%d\n", to < t ? -1 : cnt);
    return 0;
}

 

欢迎留言