贪婪算法

---

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）