整数区间 #

1. 整数区间问题的介绍
2. 整数区间问题的算法分析
3. 整数区间问题的代码实现

整数区间问题的介绍 #

给定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. 1)证明整数区间问题的贪心策略可行性
2. 2)该例与活动选择问题有何异同，请尽量说明原因