【Day 66 】2023-04-20 - 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

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

[Zoeyzyzyzy]

class Solution {
    // 首先通过排序，将附近的区间放在一起，设置第0的区间的右边界，
    // 然后根据接下来区间的左边界判断是否在前一序列的右边界里，没重叠：新的end为区间的右边界，重叠，count++,新的end为最小值（为了满足去除的重复区间尽可能小）
    //TC: O(nlogn) ->排序需要的时间 SC: O(1)
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int end = intervals[0][1];
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end)
                end = intervals[i][1];
            else {
                count++;
                end = Math.min(end, intervals[i][1]);
            }
        }
        return count;
    }
}

[NorthSeacoder]

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    let count = 1;
    intervals.sort((a, b) => a[0] - b[0]);
    let end = intervals.at(-1)[0];
    for (let i = intervals.length - 2; i >= 0; i--) {
        if (intervals[i][1] <= end) {
            count++;
            end = intervals[i][0];
        }
    }
    return intervals.length - count;
};

[LIMBO42]

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 最大的互不重叠的情况
        sort(intervals.begin(), intervals.end(), [&](const vector<int>& a, vector<int> &b){
            return a[1] < b[1];
        });
        int end = INT_MIN;
        int count = 0;
        for(int i = 0; i < intervals.size(); ++i) {
            if(intervals[i][0] >= end) {
                count++;
                end = intervals[i][1];
            }
        }
        return intervals.size() - count;
    }
};

[csthaha]

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[1] - b[1])

    let arr = [intervals[0]], temp = intervals[0]
    for(let i = 1; i < intervals.length; i++) {
        if(intervals[i][0] >= temp[1]) {
            arr.push(intervals[i])
            temp = intervals[i]
        }
    }

    return intervals.length ? intervals.length - arr.length : 0

};

[kofzhang]

思路

贪心算法，以右端点从小到大排序，依次遍历，对于每一个右端点检测是否和前一个冲突，不冲突计数+1。最终总数量-不冲突数量就是答案。

复杂度

时间复杂度：O(nlogn) 空间复杂度：On)

代码

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x : x[1])
        cnt = 0
        current = -float("inf")
        for l,r in intervals:
            if l>=current:
                cnt += 1
                current = r
        return len(intervals)-cnt

[Meisgithub]

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b)
        {
            if (a[0] == b[0])
            {
                return a[1] < b[1];
            }
            return a[0] < b[0];
        });
        int ans = 0;
        int n = intervals.size();
        int end = intervals[0][1];
        int i = 1;
        while (i < n)
        {
            if (intervals[i][0] < end)
            {
                if (intervals[i][1] <= end)
                {
                    end = intervals[i][1];
                }
                ++ans;
            }
            else
            {
                end = intervals[i][1];
            }
            ++i;
        }
        return ans;
    }
};

[FireHaoSky]

思路：贪心算法

代码：python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        right = intervals[0][1]
        ans = 1

        for i in range(1, n):
            if intervals[i][0] >= right:
                right = intervals[i][1]
                ans += 1

        return n - ans

复杂度分析：

"""
时间复杂度：O(nlogn)
空间复杂度：O(logn)
"""

[Diana21170648]

思路

贪心+二分，比较后一个的开始与前一个的结束，如果递增，直接补在后面，如果在中间，插入更长的

import bisect
class Solution:
    def lengehofLIS(self,A)->int:
        d=[]
        for start,end in range (A):
            i=bisect.bisect_left(d,end)
            if i<len(d):
                d[i]=end
            elif not d or i<=start:
                d.append(end)
        return len(d)
    def nonoverlappingintervals(self,intervals)->int:
        n=len(intervals)
        if n==0:
            return 0
        ans=1
        intervals.sort(key=lambda a:a[0])
        return n-self.lengehofLIS(intervals)

**复杂度分析**
- 时间复杂度：O(NlogN)，其中使用了排序。
- 空间复杂度：O(N)

[Abby-xu]

class Solution: #time: O(NlogN) :: sort space:O(1)
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        real_end, cnt = float('-inf'), 0
        for srt, end in sorted(intervals, key=lambda x: x[1]):
            if srt >= real_end: 
                real_end = end
            else: 
                cnt += 1
        return cnt

[harperz24]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x:x[1])
        count = 1
        prev = intervals[0]
        for interval in intervals[1:]:
            if prev[1] <= interval[0]:
                count += 1
                prev = interval
        return len(intervals) - count

[Size-of]

var eraseOverlapIntervals = function(intervals) { if (!intervals.length) { return 0; }

intervals.sort((a, b) => a[1] - b[1]);

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

};

[RestlessBreeze]

code

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        vector<int> dp(intervals.size(), 1);
        sort(intervals.begin(), intervals.end(), cmp);
        int res = 1;
        int flag = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] >= flag)
            {
                res++;
                flag = intervals[i][1];
            }
        }

        return intervals.size() - res;
    }
};

[jiujingxukong]

思路

子问题的最优解也是原问题的最优解，符合贪心算法特点。是动态规划的特例——贪心算法。

js code

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
  const l = intervals.length;
  return l - intervalSchedule(intervals);

  function intervalSchedule(intervals) {
    if (intervals.length === 0) {
      return 0;
    }
    intervals.sort((a, b) => a[1] - b[1]);
    let count = 1;
    let endTime = intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {
      let startTime = intervals[i][0];
      if (startTime >= endTime) {
        count++;
        endTime = intervals[i][1];
      }
    }
    return count;
  }
};

复杂度分析

TC：有排序，有循环一次intervals数组。时间复杂度取决于排序算法如何实现，应该是O（nlogn）,n是intervals数组长度。 SC：取决于排序算法，O（1）或者O（logn）

[zhangyu1131]

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // 贪心
        std::sort(intervals.begin(), intervals.end(), [](vector<int>& v1, vector<int>& v2)
        { return v1[1] < v2[1]; });

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

        return n - ans;
    }
};

[Jetery]

class Solution {
public:
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.size() - count;
    }
};

[snmyj]

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n=intervals.size();

        vector<int> dp(n,1);
        sort(intervals.begin(),intervals.end());
        for(int i=1;i<n;i++){

            for(int j=i-1;j>=0;j--){
                if(intervals[j][1]<=intervals[i][0]){
                    //dp[i]=dp[j]++;
                    dp[i]=dp[j]+1;
                   break;
                }

            }

        }
        sort(dp.begin(),dp.end());
        return(n-dp[n-1]);

    }
};

[huizsh]

class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: n = len(intervals) if n == 0: return 0 dp = [1] * n ans = 1 intervals.sort(key=lambda a: a[0])

    for i in range(len(intervals)):
        for j in range(i - 1, -1, -1):
            if intervals[i][0] >= intervals[j][1]:
                dp[i] = max(dp[i], dp[j] + 1)
                break # 由于是按照开始时间排序的, 因此可以剪枝

    return n - max(dp)

[kangliqi1]

class Solution: def lengthOfLIS(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.lengthOfLIS(intervals)

[Lydia61]

435. 无重叠区间

思路

贪心算法

代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return 0;
        }

        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
            return u[1] < v[1];
        });

        int n = intervals.size();
        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;
    }
};

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[GuitarYs]

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return 0;
        }

        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
            return u[1] < v[1];
        });

        int n = intervals.size();
        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;
    }
};

[bookyue]

TC: O(nlogn)
SC: O(n)

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparing(i -> i[1]));

        int res = 0;
        int i = 0;
        while (i < intervals.length) {
            int j = i + 1;
            int cur = intervals[i][1];

            while (j < intervals.length && cur > intervals[j][0]) {
                res++;
                j++;
            }

            i = j;
        }

        return res;
    }

[lp1506947671]

class Solution:
    def lengthOfLIS(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.lengthOfLIS(intervals)

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[aoxiangw]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        res = 0
        prevEnd = intervals[0][1]
        for s, e in intervals[1:]:
            if s >= prevEnd:
                prevEnd = e
            else:
                res += 1
                prevEnd = min(e, prevEnd)
        return res

time, space: O(nlogn), O(1)

[JasonQiu]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x[1])
        right = intervals[0][1]
        result = 1

        for i in range(1, len(intervals)):
            if intervals[i][0] >= right:
                result += 1
                right = intervals[i][1]

        return len(intervals) - result

Time: O(nlogn) Space: O(logn)

[enrilwang]

class Solution { // 首先通过排序，将附近的区间放在一起，设置第0的区间的右边界， // 然后根据接下来区间的左边界判断是否在前一序列的右边界里，没重叠：新的end为区间的右边界，重叠，count++,新的end为最小值（为了满足去除的重复区间尽可能小） //TC: O(nlogn) ->排序需要的时间 SC: O(1) public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[0] - b[0]); int end = intervals[0][1]; int count = 0; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] >= end) end = intervals[i][1]; else { count++; end = Math.min(end, intervals[i][1]); } } return count; } }

[joemonkeylee]

思路

在剩余区间无重叠的情况下，计算需要移除的最少区间，等价于计算可以保留的最多区间。

代码

    public int EraseOverlapIntervals(int[][] intervals)
    {
        Array.Sort(intervals, (a, b) => a[1] - b[1]);
        int eraseCount = 0;
        int end = intervals[0][1];
        int length = intervals.Length;
        for (int i = 1; i < length; i++)
        {
            if (intervals[i][0] >= end)
            {
                end = intervals[i][1];
            }
            else
            {
                eraseCount++;
            }
        }
        return eraseCount;
    }

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[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;
    }
}

复杂度分析

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

[yingchehu]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if n == 0: return 0
        dp = [1] * n
        ans = 1
        intervals.sort(key=lambda a: a[0])

        for i in range(len(intervals)):
            for j in range(i - 1, -1, -1):
                if intervals[i][0] >= intervals[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    break
        return n - max(dp)

[X1AOX1A]

class Solution:
    def lengthOfLIS(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.lengthOfLIS(intervals)

[chanceyliu]

代码

function eraseOverlapIntervals(intervals: number[][]): number {
  if (!intervals.length) {
    return 0;
  }

  intervals.sort((a, b) => a[1] - b[1]);

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