不说那些有的没的了，直接上干货~
最小区间覆盖问题
题目：视野争夺
理解：最小区间覆盖问题（给定n个区间和一个范围[a,b]，求能覆盖这个范围的最小区间数），实质上是贪心算法的一个应用。
策略：
① 初始化起始区间为[a,a]。
② 对于当前区间[x,y]，选择的下一个区间左端点值应该小于y，否则就不能完全覆盖。
③ 满足②这样的区间有很多个，此时应该“贪心”的取右端点最大的那个区间。
核心伪代码：
'''
n为可取区间数
'''
count = 0 #区间数
i = 0 #初始化起始可取区间
while i<n： # 可取区间不为0
if 当前区间右端点>=b:
return count
for j in range(i, n):
找到符合条件的下一个最大区间
if 区间左端点大于y：
break #跳出循环
if 找到了最大区间:
count+=1
y = 最大区间右端点
else:
return 0 # 无解
类似题目：
跳跃游戏II
灌溉花园的最少水龙头数目
网友评论