1288. 删除被覆盖区间

先按照起点升序排序。若起点相同，则按照终点降序排序，这样能保证下面的区间被上面的区间覆盖掉。intervals=sorted(intervals,key=lambda x: (x[0], -x[1]))
分2种情况讨论
- 完全覆盖，则计数-1 ，区间不变
- 不能覆盖，则计数不变，把区间更新到当前线段中
也可以分3种情况讨论
- 完全覆盖，则计数-1 ，区间不变
- 部分区间相交，则扩大右区间
- 完全不相交，则把区间更新到当前线段中

# 两种情况的代码
class Solution(object):
    def removeCoveredIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        if len(intervals)<=1: return len(intervals)
        intervals=sorted(intervals,key=lambda x: [x[0],-x[1]])
        record=[intervals[0][0],intervals[0][1]]
        res=len(intervals)
        for i in range(1,len(intervals)):
            if intervals[i][1]<=record[1]: # 能完全覆盖，record继续保持
                res-=1
            else: 
                record = [intervals[i][0], intervals[i][1]] # 不能覆盖，把record更新到当前的线段中
        return res



# 三种情况的代码
class Solution:
    def removeCoveredIntervals(self, intervals):
        # 按起点升序、终点降序的方式排列。排列后，必然是前面的区间覆盖后面的区间
        intervals=sorted(intervals,key=lambda x: (x[0], -x[1]))
        res = len(intervals)
        left, right = intervals[0][0], intervals[0][1]  # 以第0个线段为基准，初始化合并区间的起点和终点
        for i in range(1, len(intervals)):
            if left <= intervals[i][0] and right >= intervals[i][1]:  # 情况1：完全覆盖
                res -= 1
            if right >= intervals[i][0] and right <= intervals[i][1]:  # 情况2：区间相交，需要合并
                right = intervals[i][1]  # 扩大右区间
            if right < intervals[i][0]:  # 情况3：完全不相交，把区间跳转到当前线段中
                left = intervals[i][0]
                right = intervals[i][1]
        return res

56. 合并区间

按照区间的start，排序 intervals = sorted(intervals, key=lambda x: x[0])
如果当前的头没超过之前的尾，则取当前/ 之间尾的最大值。否则若超过了，res把当前区间添加进去。然后开始新一轮更新

# 输入: [[1,3],[2,6],[8,10],[15,18]]
# 输出: [[1,6],[8,10],[15,18]]
# 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        # if len(intervals)<=1: return len(intervals)
        intervals.sort(key=lambda x: (x[0],-x[1]))
        record=[intervals[0][0],intervals[0][1]]
        ans=[]
        for i in range(1,len(intervals)):
            if intervals[i][1]<=record[1]:
                continue
            elif intervals[i][0]>record[1]:# 当前的头超过之前的尾
                ans.append(record)
                record = [intervals[i][0], intervals[i][1]]
            elif intervals[i][0]<=record[1] and intervals[i][1]>record[1]:# 有交集，当前的尾超过之前的头
                record = [record[0], intervals[i][1]]
        ans.append(record)
        return ans
# so=Solution()
# intervals=[[1,3],[2,6],[8,10],[15,18]]
# print(so.merge(intervals))




# 或者可以合并写为：
class Solution(object):
  def merge(self, intervals):
      """
      :type intervals: List[List[int]]
      :rtype: List[List[int]]
      """
      if not intervals: return []

      intervals = sorted(intervals, key=lambda x: x[0])
      res = [intervals[0]]
      for i in range(1, len(intervals)):
          if intervals[i][0] <= res[-1][1]:
              #更新并维护当前最大区间
              res[-1][1] = max(res[-1][1], intervals[i][1])
          else:
              # 添加到结果，并重新更新
              res.append(intervals[i])
      return res

986. 区间列表的交集

找到有交集的条件，然后取公共部分
可能存在多个区间，注意更新指针的条件

class Solution(object):
    def intervalIntersection(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
        res=[]
        i,j=0,0
        while i<len(A) and j<len(B):
            a1,a2=A[i][0],A[i][1]
            b1,b2=B[j][0],B[j][1]
            if b2>=a1 and a2>=b1:# 有交集的情况
                res.append([max(a1,b1),min(a2,b2)]) # 取公共部分
            # 跳指针
            if b2<a2: j+=1
            else: i+=1
        return res