56. 合并区间

https://leetcode-cn.com/problems/merge-intervals/
其实是找互相没有交叉的区间

  1. 根据区间处理的情况判断以区间起始点排序还是终止点

  2. 此类循环注意结束后还需要再将最后状态放入结果Array中

    1. class Solution:
    2.  def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    3.      if not intervals:
    4.          return []
    5.      intervals = sorted(intervals, key=lambda a: a[0])
    6.      start = intervals[0][0]
    7.      end = intervals[0][1]
    8.      res = []
    9.      for s,e in intervals[1:]:
    10.          if s <= end:
    11.              start = min(s, start)
    12.              end = max(e, end)
    13.          else:
    14.              res.append([start,end])
    15.              start = s
    16.              end = e
    17.      res.append([start,end])
    18.      return res

    57. 插入区间 Hard

    https://leetcode-cn.com/problems/insert-interval/

    435. 无重叠区间

    https://leetcode-cn.com/problems/non-overlapping-intervals/
    本题是不要重叠的区间，所以可以和下面一题对比， 下面是要求最小可重叠的区间，关键的两个区别：

  3. 用左边界还是右边界排序

  4. 边界交叉的条件 (< or <=)
    1. class Solution:
    2.  def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    3.      if len(intervals) < 2:
    4.          return 0
    5.      count = 0
    6.      intervals = sorted(intervals, key = lambda a:a[1])
    7.      start = intervals[0][0]
    8.      end = intervals[0][1]
    9.      for s,e in intervals[1:]:
    10.          if s < end:
    11.              count+=1
    12.          else:
    13.              end = e
    14.      return count

452. 用最少数量的箭引爆气球

https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
这道题关键是用左边界排序， 当后一个区间左边界触及前一个区间的右边界时，压缩区间，取两个区间overlap的部分

  1. class Solution:
  2.     def findMinArrowShots(self, points: List[List[int]]) -> int:
  3.         if len(points) < 2:
  4.             return len(points)
  5.         points = sorted(points, key = lambda a:a[0])
  6.         arrows = len(points)
  7.         end = points[0][1]
  8.         for s,e in points[1:]:
  9.             if s <= end:
  10.                 end = min(end,e)
  11.                 arrows-=1
  12.             else:
  13.                 end = e
  14.         return arrows

253. 会议室 II

https://leetcode-cn.com/problems/meeting-rooms-ii/
题目就是要统计同一时刻进行的最大会议的数量
我们可以把所有的开始时间和结束时间放在一起排序，
用cur表示当前进行的会议数量，遍历排序后的时间数组
如果是开始时间，cur加1，如果是结束时间，cur减一
在遍历的过程中，cur出现的最大值就是需要的房间数
如果一个会议结束的时候和一个会议开始的时间相同，主要要让一个先结束，一个再开始

  1. class Solution:
  2.     def minMeetingRooms(self, intervals: List[List[int]]) -> int:
  3.         if not intervals:
  4.             return 0
  5.         events = list(zip(*intervals))
  6.         events = [(x,1) for x in events[0]] + [(x,-1) for x in events[1]]
  7.         events.sort()
  8.         cur = 0
  9.         ans = 0
  10.         for _, e in events:
  11.             cur+=e
  12.             ans = max(cur,ans)
  13.         return ans