【Day 66 】2023-08-14 - 435. 无重叠区间

[azl397985856]

435. 无重叠区间

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/non-overlapping-intervals/

前置知识

暂无

题目描述

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 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

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

[freesan44]

class Solution {
    func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
        let n = intervals.count
    if n == 0 {
        return 0
    }

    var dp = [Int](repeating: 1, count: n)
    var ans = 1
    var sortedIntervals = intervals.sorted { $0[0] < $1[0] }

    for i in 0..<n {
        for j in (0..<i).reversed() {
            if sortedIntervals[i][0] >= sortedIntervals[j][1] {
                dp[i] = max(dp[i], dp[j] + 1)
                break // 由于是按照开始时间排序的，因此可以剪枝
            }
        }
    }

    return n - dp.max()!
    }
}

[Diana21170648]

思路

lis

代码

class Solution:
    def LIS(SELF,A:List[int])->int:
        d=[]#存储最长递增子序列的元素
        for s,e in A:
            i=bisect.bisect_left(d,e)
            if i<len(d):
                d[i]=e
            elif not d or d[-1]<=s:
                d.append(e)
        return len(d)
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n=len(intervals)
        if n==0:
            return 0
        ans=1#至少考虑一个不重叠的区间
        intervals.sort(key=lambda a:a[0])
        return n-self.LIS(intervals)

复杂度分析

• 时间复杂度：O(NlogN)，其中 N 为数组长度。
• 空间复杂度：O(N)

[GuitarYs]

class Solution:
    def eraseOverlapIntervals(self, intervals):
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        count = 1  
        end = intervals[0][1]  
        for i in range(1, len(intervals)):
            start = intervals[i][0]
            if start >= end:
                count += 1
                end = intervals[i][1]
        return len(intervals) - count

[Beanza]

class Solution { func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int { let n = intervals.count if n == 0 { return 0 }

var dp = [Int](repeating: 1, count: n)
var ans = 1
var sortedIntervals = intervals.sorted { $0[0] < $1[0] }

for i in 0..<n {
    for j in (0..<i).reversed() {
        if sortedIntervals[i][0] >= sortedIntervals[j][1] {
            dp[i] = max(dp[i], dp[j] + 1)
            break // 由于是按照开始时间排序的，因此可以剪枝
        }
    }
}

return n - dp.max()!
}

}

[Fuku-L]

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0){
            return 0;
        }

        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] interval1, int[] interval2){
                return interval1[1] - interval2[1];
            }
        });

        int n = intervals.length;
        int right = intervals[0][1];
        int ans = 1;
        for(int i = 1; i<n; i++){
            if(intervals[i][0] >= right){
                ans++;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }
}

[Alexno1no2]

# 贪心思想：先留下右边界最小的区间，再去除重复区间

# 根据区间右边界升序排列；
# 维护right，代表已留下区间的最大右边界；
# 遍历排序后的区间：
# 如果当前区间的左边界 ≥ right，该区间可以留下，更新right
# 如果当前区间的左边界 < right，该区间去除，更新结果res

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key = lambda x : x[1])
        res = 0
        right = intervals[0][1]
        for i in range(1, len(intervals)):
            if intervals[i][0] < right:
                res += 1
            else:
                right = intervals[i][1]
        return res

[Momogir]

#基本思想 选择右端点最小的区间1作为左侧区间，再选择与区间1不重合的右侧端点最小的区间，剩余部分主要在代码实现上
#时间复杂度排序O（nlogn）+遍历O（n）=O（nlogn）
#空间负责度排序O（nlogn）
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
       intervals.sort(key=lambda x: [x[1],x[0]])
       head=intervals[0]
       cnt=1

       n=len(intervals)
       for i in range(1,n):
           if intervals[i][0]>=head[1]:
               cnt+=1
               head=intervals[i]
       return n-cnt