整数区间 #
- 整数区间问题的介绍
- 整数区间问题的算法分析
- 整数区间问题的代码实现
整数区间问题的介绍 #
给定n个闭区间[ai,bi],在数轴上选尽量少的的点,使得每个区间内至少含有一个点。
例如:给定4个闭区间,[3,6]、[2,4]、[0,2]、[4,7],那么在数轴上选取点集合S={2,6},即只需要选取两个点即可以在四个区间上都能找到至少{2,6}的一个点
整数区间的算法分析 #
贪心策略的制定:第一次选择选取整数区间结束最早的bi,第二步选择不包含该点的剩下的整数区间的结束最早的bi,以此类推。该题的贪心策略制定与活动选择问题是一致的,事实上该问题和活动选择问题是一样的。因为该问题等价于在给定的区间中找出尽可能多的,不重合的整数区间。
1)首先将整数区间按照b1<=b2<=……<=bn排列
2)选取b1点,然后选择不包含该点的整数区间的结束最早的点,以此类推
该策略的证明,可以参考287课活动选择2的证明,这里不在赘述
整数区间的代码实现 #
d=[[3,6],[2,4],[0,2],[4,7]]#坐标区间 sd=sorted(d,key=lambda x:x[1])#坐标区间按照bi从小到大排列,也可自行按照排序算法排序 res=[sd[0][1]]#保留每步结果,首先选择b1 for i in sd[1:]: if(i[0]>res[-1]):#如果当前区间不包含上一标记点添加 res.append(i[1]) print(res)
小结 #
- 根据整数区间问题,理解贪心算法
- 掌握整数区间求解的贪心算法,能够根据实际问题作出合适的贪心策略
习题 #
- 1)证明整数区间问题的贪心策略可行性
- 2)该例与活动选择问题有何异同,请尽量说明原因