V8作为一个Dota lover，因为在某次和小伙伴开黑对战“简单的电脑”时被电脑血虐，V8痛定思痛之后，发现是时候学一发Dota教学视频了。现在，V8在网上找到了n个Dota直播教学视频，并且知道每个视频的开始时间和结束时间，现在V8想知道他作出合理安排之后他最多看多少个完整的Dota视频。
V8作为一个Dota lover，因为在某次和小伙伴开黑对战“简单的电脑”时被电脑血虐，V8痛定思痛之后，发现是时候学一发Dota教学视频了。现在，V8在网上找到了n个Dota直播教学视频，并且知道每个视频的开始时间和结束时间，现在V8想知道他作出合理安排之后他最多看多少个完整的Dota视频。
多组数据，n==0时文件结束。每组数据第一行一个数字n（1<=n<=10^3）,接下来n行每行两个数字li，ri，表示视频的开始时间和结束时间（0<=li<=ri<=2*10^4）。
每组数据一行输出，表示V8最多能看到的完整教学视频的数量。
--正文
贪心的线段覆盖问题，换了个皮
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct VideoNode { int begin; int end; }; struct VideoNode video[1001]; int cmp(struct VideoNode v1,struct VideoNode v2){ return (v1.end < v2.end); } int main(){ int n; while (scanf("%d",&n) != EOF){ if (n == 0) break; int i; for (i=0;i<n;i++){ int begin,end; scanf("%d %d",&begin,&end); video[i].begin = begin; video[i].end = end; } sort(video,video+n,cmp); int total = 0,time = -1; for (i=0;i<n;i++){ if (video[i].begin >= time){ time = video[i].end; total ++; } } printf("%d\n",total); } return 0; }
原文：http://www.cnblogs.com/ToTOrz/p/6106580.html