leetcode435 Non-overlapping Intervals

leetcode435 Non-overlapping Intervals

题目

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

You may assume the interval's end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:

Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

意思是给了一些区间的集合,这里的区间是个定义好的类,有左端点和右端点,然后问的是最少去掉多少个区间,使得剩下的区间不再overlap,其中端点重合的不算overlap, 还给了三种情况的例子。

这个题的思路和之前做过的几个区间问题有些类似,也是先将所有的区间按照start进行从低到高的排序,排序好了之后再从第一个开始往下看,看看有没有相交,如果相交的话,结果就加1,但是应该删除哪一个呢,因为我们想要尽可能地删除地少一些,所以会选择去掉那个大一些的,其实在写代码的时候并不是真正的删了,而是那个对比的’last’在不断地更新,而见到这种情况的时候,就把它更新为end较小的那一个,如果和当前的没有交集的话就更新为当前的这一个。

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        intervals = sorted(intervals, key=lambda x:x.start)
        
        last = 0
        res = 0
        
        for i in range(1, len(intervals)):
            if intervals[last].end > intervals[i].start:
                res += 1
                # 为了删除的数目较少,删除end较大的那一个
                if intervals[last].end > intervals[i].end:
                    last = i
            else:
                # 这种情况下也要更新last
                last = i
                
        return res

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦