435.md

435 Non-overlapping Intervals

Description

link

---

Solution

这题的一开始我是使用每一个interval的start来进行排序的，这样需要做多一步操作就是当当前的interval重合时，我们需要更新最小的右边界以保持贪心的正确性，能留出最大的空间保证不重合

而如果通过interval的end来进行排序的话，由于一开始就是排序好的，就算是有重合的情况下，由于end是排序好的，所以能保证一定能留下最大的空间，PS指定了key之后剩下的按照默认来，也就是说同样的end情况下会按照start顺序来，这样就没有问题了

---

Code

Complexity T : O((log(n))

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals)
        count = 0
        last_border = float("-inf")
        for l, r in intervals:
            if l >= last_border:
                last_border = r
            else:
                count += 1
                last_border = min(last_border, r)
        return count


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda x: x[1])
        count = 0
        last_border = float("-inf")
        for l, r in intervals:
            if l >= last_border:
                last_border = r
            else:
                count += 1
        return count