贪心算法是一种高效算法，可以快速得到问题的答案。如果一个问题可以用贪心法解决，那么它必须具备2条性质：1.具有最优子结构（即问题的最优解包含了子问题的最优解），2.具有贪心选择性质（即可以通过做出局部最优选择来构造全局最优）。下面总结一下基于贪心算法的区间问题。
1.问题描述：数轴上有n个开区间(Ai,Bi)，选择尽量多个区间，使得这些区间两两没有公共点。
样例输入：n=5, (1,3),(2,5),(4,7),(6,9),(8,10)。
样例输出：3 (选择第1,3,5个区间)
2.贪心策略：按照终点从小到大给区间排序，然后从第一个区间开始选择。
3.代码：
const int N=100000+10;
int n,s[N],t[N];
int main()
{
while(~scanf("%d",&n))
{
me(s);me(t);
for(int i=0;iv;
for(int i=0;i
二，区间选点问题
1.问题描述：数轴上有n个闭区间[Ai,Bi]，取尽量少的点，使得每个区间都至少有一个点。
样例输入：n=5, [1,5], [8,9], [4,7], [2,6], [3,5]
样例输出：2 （选择点5,9即可）
2.贪心策略：把所有区间按照B从小到大排序，如果B相同，按照A从大到小排序，每次都取第一个区间中的最后一个点。
3.代码：
const int N=10000+10;
struct Node
{
int L,R;
bool operator<(const Node&rhs)const
{
return Rrhs.L);
}
}a[N];
int main()
{
int n;
while(~scanf("%d",&n))
{
me(a);
for(int i=0;i
三，区间覆盖问题
1.问题描述：数轴上有n个闭区间[Ai,Bi]，选择尽量少的区间覆盖一条指定的线段[s,t]。
样例输入：n=5, [1,6], [7,13], [8,9], [4,7], [5,8]，被覆盖的区间：[5,10]
样例输出：2 （选择第2,4即可完成覆盖）
2.贪心策略：首先进行预处理，把和[s,t]区间有交集的区间取出，按照A从小到大排序，如果第一个区间起点不是s，则无解；否则选择起点在s的最长的区间，新的起点设置为该区间的终点，然后继续重复上述过程，直到终点大于等于t结束。
3.代码：
略