题干：

“今年暑假不AC？” 
“是的。” 
“那你干什么呢？” 
“看世界杯呀，笨蛋！” 
“@#$%^&*%...” 

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。 
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目） 
Input输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。 
Output对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。Sample Input 
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
Sample Output 
5


解题报告：

    本题只需要维护end变量就好。


//只需维护end！！ 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

struct Node {
	int s,e;
} node[100+5];
bool cmp(const Node & a, const Node &b) {
	if(a.e!=b.e) return a.e<b.e;
	else return a.s<b.s;
}
int main()
{
	int n;
	int ans;
//	freopen("in.txt","r",stdin);
	while(~scanf("%d",&n) && n ) {
		ans=1;
		for(int i = 0; i<n; i++) {
			scanf("%d %d",&node[i].s,&node[i].e);
		}
		sort(node,node+n,cmp);
		int r=node[0].e;
		for(int i = 1; i<n; i++) {
			if(node[i].s>=r) {
				ans++;
				r=node[i].e;
			}
		}
		printf("%d\n",ans);	
	}
	return 0 ;
 }


（ps：一会来一波区间问题汇总。）


问题2：

问题描述：

设有n个会议的集合C={1,2,…,n}，其中每个会议都要求使用同一个资源（如会议室），而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei，且bi < ei 。如果选择了会议i使用会议室，则它在半开区间[bi, ei)内占用该资源。如果[bi, ei)与[bj , ej)不相交，则称会议i与会议j是相容的。会场安排问题要求在所给的会议集合中选出最大的相容活动子集，也即尽可能地选择更多的会议来使用资源。


贪心策略：

（1）选择最早开始时间且不与已安排会议重叠的会议
（2）选择使用时间最短且不与已安排会议重叠的会议
（3）选择具有最早结束时间且不与已安排会议重叠的会议 

仔细分析三种策略后发现，第三种策略是最优的，所以我们将此作为我们的贪心策略。


问题3：（解题链接：https://blog.csdn.net/qq_41289920/article/details/81003873）

会场安排问题

时间限制： 3000 ms  |  内存限制： 65535 KB
难度： 3
<dl class="problem&#45;display" style="font&#45;size&#58;14px&#59;color&#58;rgb&#40;70&#44;70&#44;70&#41;&#59;font&#45;family&#58;Tahoma&#44; Arial&#44; sans&#45;serif&#44; simsun&#59;background&#45;color&#58;rgb&#40;255&#44;255&#44;255&#41;&#59;"> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 描述 </dt> <dd style="margin&#45;left&#58;0px&#59;"> 学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
</dd> </dl> <dl class="others" style="color&#58;rgb&#40;51&#44;51&#44;51&#41;&#59;font&#45;family&#58;&#39;&#45;apple&#45;system&#39;&#44; &#39;SF UI Text&#39;&#44; Arial&#44; &#39;PingFang SC&#39;&#44; &#39;Hiragino Sans GB&#39;&#44; &#39;Microsoft YaHei&#39;&#44; &#39;WenQuanYi Micro Hei&#39;&#44; sans&#45;serif&#44; SimHei&#44; SimSun&#59;font&#45;size&#58;14px&#59;background&#45;color&#58;rgb&#40;255&#44;255&#44;255&#41;&#59;"> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 输入 </dt> <dd style="margin&#45;left&#58;0px&#59;"> 第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)
</dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 输出 </dt> <dd style="margin&#45;left&#58;0px&#59;"> 对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行 </dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 样例输入 </dt> <dd style="margin&#45;left&#58;0px&#59;"> 
2
2
1 10
10 11
3
1 10
10 11
11 20
</dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 样例输出 </dt> <dd style="margin&#45;left&#58;0px&#59;"> 
1
2
</dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;"> 提示 </dt> </dl>

注意：如果上一个活动在t时间结束，下一个活动最早应该在t+1时间开始


经典贪心算法，之所以按结束时间来排列，是通过数学归纳法来确定的;

通过数学归纳法可以比较出：以开始时间排列 ，以会议时间长度排列，以结束时间排列中，按结束时间排列可以得出最优解;

按这种方法选择相容活动为未安排活动留下尽可能多的时间，即局部最优;