LeetCode 435. Non-overlapping Intervals

Description

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

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.

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.

思路

  • 对每个区间按照起始位置从小到大排序。
  • 对于两个区间,如果前一个区间的结尾位置大于后一个区间的起始位置,说明存在重叠,需要去除重复。
  • 为了尽量减少去重的区间,我们选择去掉结尾位置靠后的区间。在实际的代码中,我们不需要真的删除区间,用一个变量指向上一个保留的区间就可以了。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2020-03-31 19:18:41
# @Last Modified by:   何睿
# @Last Modified time: 2020-04-01 15:23:00
rom typing import List


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key=lambda x: x[0])
        count = 0
        last = 0
        for i in range(1, len(intervals)):
            # 上一个区间的 end 大于下一个区间的 start,说明有重叠
            if intervals[last][1] > intervals[i][0]:
                count += 1
                # 保留区间中 end 较小的那一个
                if intervals[last][1] >= intervals[i][1]:
                    last = i
            # 没有重叠,last 指向下一个区间
            else:
                last = i

        return count

源代码文件在 这里 。


©本文是原创文章,欢迎转载,转载需保留 文章来源 ,作者信息和本声明.

Posted in LeetCode and tagged .

花若盛開,蝴蝶自來. 分享学习,每天进步一点点

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.