435. 无重叠区间

Difficulty
Medium
Tags
扫描线
URL
https://leetcode-cn.com/problems/non-overlapping-intervals/
Star
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
  1. 可以认为区间的终点总是大于它的起点。
  1. 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
通过次数88,609提交次数173,781

法1 扫描线

思路
将区间按照结束时间排列如下图所示排列：
notion imagenotion image
可见，会发生重叠区间的 有 ab 和 bc cd三种情况。发生重叠了当然是删除晚结束了，这样后续的才有更多的空间，即后续发生重叠的可能性才小。因为要删除晚结束的，所以这里根据结束时间排序。但是其实这里按照开始时间排序也是可以的。只是当有冲突时，需要选择结束较早的更新为当前区间。
只需要判断当前的结束时间和下一个的开始时间即可判断是否重叠：
case 1： cur = a ,next = b. cur[1]> next[0] 发生了重叠，
此时应当删除b， 此时计数器加1，然后cur保持不变即相当于已删除了b
case 2 :同上
题解
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) <= 1:
            return 0
        
        intervals.sort(key=lambda x:(x[1], x[0]))
        count = 0
        cur = intervals[0]
        for next in intervals[1:]:
            if next[0] < cur[1]:
                # 此时需要移除 next 
                # 不用更新cur即相当于移除了next,同时count += 1
                count += 1
            else:
                cur = next
        return count

# 采用开始时间升序排列
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) <= 1:
            return 0
        count = 0
        intervals.sort(key=lambda x:x[0])
        curInteval = intervals[0]
        for next_ in intervals[1:]:
            # 需要删除一个区间
            if curInteval[1] > next_[0]:
                count += 1
                # 如果是当前区间结束早，那么next_就是要删除的
                # 所以当作删除了就好了，不用更新cur区间
                if curInteval[1] < next_[1]:
                    continue
            curInteval = next_
                
        return count