题目链接： POJ 2376-Cleaning Shifts
题目大意：
给定 N 个小区间 [xi,yi]...[xn,yn] , 要求用最少的区间，覆盖大区间 [1,T]
输入格式：
第1行， N 和 T 两个数字 地2～N+1行， 每行两个数字， xi,yi
输出格式：
一个数字， 表示覆盖整个区间 [1,T] 需要的最少的区间数。
题解：
基于区间的贪心。每次都选择当前最优的那个区间，最后得到的也是最优的结果。先给区间按照开始时间升序排序，每次确定一个区间 [xi,yi] 时， 下一个要选的区间 [xk,yk] , 其中 xi<xk<=yi+1 , 选择 yk 最大的那个。 因为区间的开始小于等于 xi 的最优解就是 [xi,yi] , 已经选出来了， 所以下一个区间应该从那些 xi<xk<=yi 或者 xk=yi+1 中的区间里选择。这样才能保证整个区间都被覆盖， 没有遗漏。
代码：
#include <iostream> #include <cstdio> #include <algorithm> #define MAXN 25010 using namespace std; struct Cow { int begin, end; }cow[MAXN]; int N, T; int ans = 0; bool cmp(const Cow &a, const Cow &b) { return a.begin < b.begin; } int main() { scanf("%d%d", &N, &T); for (int i = 1; i <= N; i++) scanf("%d%d", &cow[i].begin, &cow[i].end); sort(cow, cow+N, cmp); int y = 0; //目前可以覆盖的最大的长度 ans = 0; //需要的区间数 for (int i = 1; i <= N; i++) { int max_y = y; int k = i; for (int j = i; cow[j].begin <= y+1 && j <= N; j++) { if (cow[j].end > max_y) { k = j; max_y = cow[j].end; } } if (max_y > y) { i = k; y = max_y; ans++; } else break; //可覆盖的范围没有拓展，则退出 } if (y < T) cout << -1 << endl; else cout << ans << endl; return 0; }