区间选点+区间覆盖
将这些区间[l,r]先依照r从小到大排序，再依照l从大到小排序。选点尽可能选择靠近右侧界的点。然后依照这个排序后的区间进行遍历，用1个变量来寄存遍历进程中上个区间的右侧界，然后碰到1个新的区间的时候需要分两种情况讨论：1、这个区间和上个区间有相交的部份，那末就需要判断1下上次选择的点有多少在这个区间内，这些点满足要求吗？不满足的话还需要在这个区间内选点2、这个区间和上个区间没有交集，那末这个区间就需要选点。
上述策略可以保证右侧界相同的区间，先选择区间短的那个。由于短区间的点被选择了，那末相同右侧界的更大的区间肯定包括这个比较小的区间选择的所有点，这样这个大点的区间被满足的可能性就比较大了。并且这里选点的策略是取尽可能靠近右侧界的点，这样选取被满足区间个数会是最大的。
interval[maxn][2];
sort(interval, interval + maxn, cmp);//cmp依照r小l大优先级高来排列
pre = interval[1][0] - 1; //制造出不相交的右侧界
for in range(1, maxn):
if interval[i][0] > pre://不相交
//靠近右侧界选点
else:
//先查找这个区间已被选中了多少点,然后根据是不是满足要求再进行选点
pre = interval[1][1]； //更新右侧界
else:;
题目：uva10148Advertisement（区间选点）
假定覆盖的区间是[m, n].先预先处理掉和[m,n]不沾边的区间。把出发点小的区间放前面，如果出发点相同的区间就把长的区间放前面。做两个特判，判断出发点最早的区间是不是涵盖m，和最后的覆盖是不是有覆盖到n。接着就是中间的判断了，中间的判断看代码吧。
interval[maxn][2];
vis[maxn];//记录哪条边被选择
//删除和[m, n]不沾边的区间,并且依照l小r大优先级高排序
function Cover_Interval:
if interval[0][0] < m //是不是涵盖m
return false;
pre = m;//前1个选择区间的右侧界，也是下个要选择区间的有效的起始边界
t = -1;//记录前1个区间的下标，由于可能这个区间其实不是最好的区间
cover = m - 1;//目前已覆盖了的位置
for in range(1, maxn):
if interval[i][0] <= pre: //满足最少覆盖到上个区间右侧界pre，使得全部覆盖的区间不会断开
if interval[i][1] > cover: //选取最长的满足上面的要求的区间
vis[i] = 1;
cover = interval[i][1]; //更新覆盖位置
if t != -1: //上次选中的取消
vis[t] = 0;
else: //不满足要求说明需要选择下个新的区间，更新pre
pre = cover;
if interval[i][0] > pre: //如果当前这个区间的左侧界比覆盖位置更大，那末说明中间有1段是覆盖不到的
return false;
t = -1; //新的区间清空上次选中
i--;
if cover >= n:
break;
else:;
if cover < n
return false;
//输出被选择的区间according to vis[maxn]
return true;
function end;
题目：uva10020 - Minimal coverage（区间覆盖）uva10382 - Watering Grass（区间覆盖变形）
上一篇 关于人工神经网络的两个想法
下一篇 Android系统架构剖析（一）
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
