题目地址:http://poj.org/problem?id=2376

题目大意

题目大意是,给一个个小区间,以及一个T,用最小数量的小区间覆盖至$[1, T]$。求出最小数量,否则输出-1。

思路

完蛋了,看错题目卡了好久-.-。区间$[1, 7]$和区间$[8, 10]$也能合并= =端点问题卡了。。

首先将区间按照起点从小到大排序,然后终点也按从小到大排序。在t(当前选择的区间终点)+1>=s的中选择最大的终点来更新t,最后更新次数即为答案。

AC代码

/*************************************************************************
    > File Name: 2376.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-09-02 三 09:25:34 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

struct interval {
    int s, e;
    bool operator<(const interval &b) const {
        if(s == b.s)
            return e < b.e; // 终点从小到大
        return s < b.s; // 起点从小到大
    }
} I[25010];
int N, T;

void solve() {
    scanf("%d%d", &N, &T);
    int maxe = 0, mins = 1<<30;
    for(int i=0; i<N; ++i) {
        scanf("%d%d", &I[i].s, &I[i].e);
        maxe = max(maxe, I[i].e);
        mins = min(mins, I[i].s);
    }
    if(maxe < T || mins > 1) { // 无法完成
        printf("-1\n");
        return;
    }
    sort(I, I+N);
    int j = 0;
    int t = I[j].e;
    while(I[j].s == 1) { // 选择起点为1, 终点最大的那个区间
        t = I[j].e;
        ++j;
    }
    int ans = 1;
    int maxt = -1; // 该区间后面满足要求最大的t。

    for(int i=j; i<N; ++i) {
        if(t >= T) break; // 覆盖完成
        if(I[i].s > t+1) { // 无法覆盖
            ans = -1;
            break;
        }

        if(maxt == -1) maxt = I[i].e; 
        if(i+1 < N && I[i+1].s <= t+1) { // 从满足条件中选择一个最大的e
            maxt = max(maxt, I[i+1].e);
            continue;
        }
        else  { // 更新t
            t = maxt;
            maxt = -1;
            ++ans;
        }
    }
    if(t < T)
        ans = -1;

    cout << ans << endl;

}

int main()
{
#ifdef Oj
    freopen("2376.in", "r", stdin);
#endif
    solve();
    return 0;
}