#贪心算法
class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        if not intervals:                  #注意边界条件
            return 0
        intervals.sort(key=lambda x:x[1])  #对列表排序时，传入sort函数的对象是列表中的一级子元素，所以用lambda函数来写的话，传入对象为x，
        #用于排序键为x[1]
        right=intervals[0][1]
        n=len(intervals)
        size=1
        i=1
        while(i<n):
            if(intervals[i][0]>=right):   #区间间仅有端点相交的时候，不算重合，这里判断时需要
                size+=1
                right=intervals[i][1]
            i+=1

        return n-size
      
#对贪心算法的理解
#问法方面：通常涉及到最值，即不同的选择会带来不同的结果，这跟答案固定类型的问题不同。
#解法方面：官方说法是将一个大问题拆分为一个个子问题，每个子问题选最优解，但是这个拆分的过程实际是非常有技巧的，
#在不同的题目中，要找准最优的对象，比如说在小孩子吃苹果这个问题中，子问题就是每个小孩子吃最多苹果，然后在本题中，
#他的问题对象是有多少不相覆盖的区间，拆出来的子问题是去掉一个区间后，剩下的又是一个完整的新线段，在确定分离了一个
#区间的前提外，剩下的区间长度越长，包含的区间数目大概率越多。但是跟小孩子分苹果不那么一样的是，切分第一个区间
#之后，剩余留下的长度跟你第一刀如何切分是有关系的。所以这道题的最优就体现在如何选择切分的位置。这种贪心算法
#有点像是纵向贪心，虽然结果有间接相关性，但是又不是直接的关联，即第一刀确定了之后，第二刀的选择是跟第一刀
#的位置无关，即第一刀的选择与新的子问题有关，但是跟子问题的结果无关。

b363ecfd37cb23918e01dc259a2ec3da491bbfe6
<mask token>

class Solution(object):
    <mask token>

class Solution(object):

    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        right = intervals[0][1]
        n = len(intervals)
        size = 1
        i = 1
        while i < n:
            if intervals[i][0] >= right:
                size += 1
                right = intervals[i][1]
            i += 1
        return n - size

#贪心算法
class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        if not intervals:                  #注意边界条件
            return 0
        intervals.sort(key=lambda x:x[1])  #对列表排序时，传入sort函数的对象是列表中的一级子元素，所以用lambda函数来写的话，传入对象为x，
        #用于排序键为x[1]
        right=intervals[0][1]
        n=len(intervals)
        size=1
        i=1
        while(i<n):
            if(intervals[i][0]>=right):   #区间间仅有端点相交的时候，不算重合，这里判断时需要
                size+=1
                right=intervals[i][1]
            i+=1

        return n-size
      
#对贪心算法的理解
#问法方面：通常涉及到最值，即不同的选择会带来不同的结果，这跟答案固定类型的问题不同。
#解法方面：官方说法是将一个大问题拆分为一个个子问题，每个子问题选最优解，但是这个拆分的过程实际是非常有技巧的，
#在不同的题目中，要找准最优的对象，比如说在小孩子吃苹果这个问题中，子问题就是每个小孩子吃最多苹果，然后在本题中，
#他的问题对象是有多少不相覆盖的区间，拆出来的子问题是去掉一个区间后，剩下的又是一个完整的新线段，在确定分离了一个
#区间的前提外，剩下的区间长度越长，包含的区间数目大概率越多。但是跟小孩子分苹果不那么一样的是，切分第一个区间
#之后，剩余留下的长度跟你第一刀如何切分是有关系的。所以这道题的最优就体现在如何选择切分的位置。这种贪心算法
#有点像是纵向贪心，虽然结果有间接相关性，但是又不是直接的关联，即第一刀确定了之后，第二刀的选择是跟第一刀
#的位置无关，即第一刀的选择与新的子问题有关，但是跟子问题的结果无关。
