435. Non-overlapping Intervals

题目要求：

解题思路：

• 上次打气球那给题目是按照第二个元素排序
• 这次是按照第一个元素进行排序！！！

代码：

class Interval(object):
    def __init__(self, s=0, t=0):
        self.start = s
        self.end = t


class Solution(object):
    def earseOverInterval(self, intervals):
        """
        :param intervals: List[Interval]
        :return:int
        """
        # intervals.sort(key=lambda interval: interval.start)
        intervals.sort(key=lambda interval: interval.start)

        result, prev = 0, 0
        for i in range(1, len(intervals)):
            if intervals[i].start < intervals[prev].end:
                if intervals[i].end < intervals[prev].end:
                    prev = i
                result += 1
            else:
                prev = i

        return result


    def eraseOverlapIntervalstwo(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        intervals.sort(key=lambda interval: interval.start)
        result, prev = 0, 0
        for i in range(1, len(intervals)):
            if intervals[i].start < intervals[prev].end:
                if intervals[i].end < intervals[prev].end:  #这个可以勉强称为贪心吧，画图理解
                    prev = i
                result += 1
            else:
                prev = i
        return result


if __name__ == "__main__":
    print(Solution.eraseOverlapIntervalstwo(self=None, intervals=[[1,2], [2,3], [3,4], [1,3]]))