LeetCode 435. 无重叠区间

示例 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

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        length = len(intervals)
        intervals.sort(key= lambda x:x[0])
        dp = [1] * length
        for i in range(length):
            for j in range(i-1,-1,-1):
                # print(intervals[i],intervals[j],dp)
                startTime = intervals[i][0]
                endTime = intervals[j][1]
                #如果符合递增，就放入dp中，形成完美递增序列
                if startTime >= endTime:
                    dp[i] = max(dp[i],dp[j]+1)
                    break
        # print(dp)
        return length - max(dp)

if __name__ == '__main__':
    nums = [ [1,2], [2,3], [3,4], [1,3] ]
    nums = [[1, 2], [1, 2], [1, 2]]
    nums = [[1, 2], [2, 3]]
    nums = [[1, 2], [2, 3], [3, 4], [1, 3]]
    nums = [[1,100],[11,22],[1,11],[2,12]]
    res = Solution().eraseOverlapIntervals(nums)
    print(res)