http://poj.org/problem?id=2376
Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.
Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.
Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.
http://www.hankcs.com/program/cpp/poj-2376-cleaning-shifts-challenge-programming-contest-2nd-edition-exercises-answers.html
给定N个小区间以及区间起点终点，求能用它们覆盖区间[1,T]的最小组合。
贪心策略是从左往右，尽量选择长度最大的区间。
首先对所有奶牛排序，按照开始时间排序。
然后更新起点=终点+1，搜索剩下的奶牛中能够覆盖这个起点同时终点最远的那一头，更新终点。
http://blog.csdn.net/nvfumayx/article/details/6876989
Read full article from 2376 -- Cleaning Shifts
Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.
Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.
Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.
http://www.hankcs.com/program/cpp/poj-2376-cleaning-shifts-challenge-programming-contest-2nd-edition-exercises-answers.html
给定N个小区间以及区间起点终点，求能用它们覆盖区间[1,T]的最小组合。
贪心策略是从左往右，尽量选择长度最大的区间。
首先对所有奶牛排序，按照开始时间排序。
然后更新起点=终点+1，搜索剩下的奶牛中能够覆盖这个起点同时终点最远的那一头，更新终点。
http://blog.csdn.net/nvfumayx/article/details/6876989
题意：给出区间[ 1,T ]和N个小区间，要求用尽可能少的小区间覆盖区间[ 1,T ]，输出最少的小区间数量；若不能覆盖，输出-1。
思路：贪心。
具体：令begin为当前未被覆盖的区间起点。
贪心策略：选取包含点begin的区间中右端点最大的那个；若不存在包含begin的区间，输出-1。
证明：因为begin为未被覆盖的区间起点，所以begin一定要被小区间覆盖，将最优解中覆盖begin的小区间命名为区间X。
以下使用剪贴技术证明。
若存在包含begin的小区间Y( Y != X )使最终所需的小区间数少于原最优解，那么Y一定包含了X之后的某些小区间，
即Y的右端点大于X的右端点，与贪心策略矛盾，得证。
int N, T;struct Cow{ int begin; // 开始时间 int end; // 结束时间 };#define MAX_COWS 25000Cow cow[MAX_COWS];bool is_greater(const Cow& a, const Cow& b){ return a.begin < b.begin || (a.begin == b.begin && a.end > b.end);}int solve(){ int used_cows = 0; int end = 0; int index = 0; while(end < T) { int begin = end + 1; // 寻找一头既能从begin干起，又能一直干到最远的牛 for (int i = index; i < N; ++i) { if (cow[i].begin <= begin) { // 能够覆盖起始点 if (cow[i].end >= begin) { // 将终点延长到最远 end = max(end, cow[i].end); } } else { // 不能覆盖起始点，说明上一头牛的终点就是最远点，需要换一头牛了 index = i; break; } } // 没找到这样的牛，这个case失败 if (begin > end) { return -1; } else { ++used_cows; } } return used_cows;}int main(int argc, char *argv[]){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif cin >> N >> T; for (int i = 0; i < N; ++i) { cin >> cow[i].begin >> cow[i].end; } sort(cow, cow + N, is_greater); cout << solve() << endl;#ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt");#endif return 0;}