index-picture
贪婪算法：
选择局部最优解达到全局最优
区间调度问题
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
1.可以认为区间的终点总是大于它的起点。
2.区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
给定区间如下：
[ [1,2], [2,3], [3,4], [1,3] ]
实现代码：
def eraseOverlapIntervals(intervals):
if len(intervals) == 0:
return 0
intervals.sort(key = lambda x : x[1])
print (intervals)
cur = 0
count = 1
for i in range(1, len(intervals)):
if intervals[i][0] >= intervals[cur][1]:
count += 1
cur = i
return len(intervals) - count
本题来源：力扣（LeetCode）
网友评论