区间完全覆盖问题 &&区间均取最少2个点的问题
区间完全覆盖问题
例题1
描述：给定一个长度为m的区间，再给出n条线段的起点和终点（注意这里是闭区间），求最少使用多少条线段可以将整个区间完全覆盖
样例：
区间长度8，可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5]
解题过程:
1将每一个区间按照左端点递增顺序排列，拍完序后为[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]
2设置一个变量表示已经覆盖到的区域。再剩下的线段中找出所有左端点小于等于当前已经覆盖到的区域的右端点的线段中，右端点最大的线段在加入，直到已经覆盖全部的区域
3过程:
假设第一步加入[1,4]，那么下一步能够选择的有[2,6]，[3,5]，[3,6]，[3,7]，由于7最大，所以下一步选择[3,7]，最后一步只能选择[6,8]，这个时候刚好达到了8退出，所选区间为3
4贪心证明:
需要最少的线段进行覆盖，那么选取的线段必然要尽量长，而已经覆盖到的区域之前的地方已经无所谓了，（可以理解成所有的可以覆盖的左端点都是已经覆盖到的地方），那么真正能够使得线段更成的是右端点，左端点没有太大的意义，所以选择右端点来覆盖
例题2
有n个闭区间[ai,bi]，其中i=1，2，……，n。这些区间代表一系列没有交点的闭区间。任务是去寻找这些区间的代表，力求仅需最少的区间数覆盖整个区间。这些区间代表应该以上升的顺序写在输出文件。我们说区间[a，b]和[c，d]是上升的顺序是指当且仅当a≤b≤c≤d。
输入：
第一行有一个整数n，3≤n≤50000，这是区间数目。在第i+1行，1≤i≤n，有一个区间[ai,bi]的描述，描述的形式是以两个由空格分隔开的ai,bi表示，ai，bi分别表示区间的开始和结束，1≤ai≤bi≤1000000。
输出：
所有计算出的没有交点的区间。在第一行都有一个区间的描述。它包含2个整数，整数间由空格分开，区的开始与结束都是独立的。这些区间应该以上升的顺序输出。
三． 启发与总结：
将无序的区间转化成有序的区间使本题的关键。将没有条理（无序）的已知条件转化为有条理（有序）的已知条件是一种重要思想，在拿到一道无从下手的题目时这样做往往能起到很好的作用。
排序虽然在近几年不是竞赛中的热点问题，但它也经常在各种考试中出现，在许多问题中都要用到排序，所以一定要熟练掌握各种排序算法。
区间均取最少2个点的问题：
给定一个大区间[a,b]，再给出几个小区间 ，找出满足下述条件的所含元素个数最少的集合的个数，该集合满足
——对于给定的每一个区间，都至少有两个不同的整数属于该集合。
本题数据规模较大，用搜索做会超时，而动态规划无从下手。考虑贪心算法。题目意思是要找一个集合，该集合中的数的个数既要少又要和所给定的所有区间都有2个点的交集。（每个区间至少有两个该集合中的数）。我们可以从所给的区间中选数，为了选尽量少的数，应该使所选的数和更多的区间有交集这就是贪心的标准。一开始将所有区间按照右端点从小到大排序。从第一个区间开始逐个向后检查，看所选出的数与所查看的区间有无交集，有两个则跳过，只有一个数相交，就从当前区间中选出最大的一个数（即右端点），若无交集，则从当前区间选出两个数，就（右端点，右端点-1），直至最后一个区间。
[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct prince
{
int left,right;//区间左右端点
}a[10000];
int n;
int result;//存放结果中的数
int cmp(const void *a,const void *b)
{
return (*(prince *)a).right-(*(prince *)b).right;
}
int work()
{
qsort(a+1,n,sizeof(a[0]),cmp);//按区间右端点由小到大排序
int i;
int a1,a2;
a1=a[1].right-1;a2=a[1].right;result=2;
for(i=2;i<=n;i++)
{
if(a[i].left<=a1&& a[i].right>=a2)continue;//完全包含的情况下 其区间的2点就是上次的2点 直接跳过
if (a[i].left>a2 )//完全不包含 则要添加进去2点
{
a1=a[i].right-1;a2=a[i].right;result=result+2;
}
if (a[i].left>a1 && a[i].right>a2 && a[i].left<=a2)
{
a1=a2;a2=a[i].right;result++;}//只包含一个
}
return result;
}
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%d %d",&a[i].left,&a[i].right);
printf("%d\n",work());
return 0;
}
补充：软件开发 , C++ ,
