【Day 66 】2022-02-15 - 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

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

[yetfan]

思路 以右边界为key将区间进行排序，我们要找到一个右区间 right 最小的，以保证该点以后的区间数最多。 有了第一个区间，就同理继续找下一个右区间最小 且不与第一区间重合的。 遍历，排除所有左边界再跟第一区间有所重叠的，直到找到下一个 左边界 >= right的区间，计数+1。 最后总数减去最多可以同时存在的不重叠区间数 即为所求。

代码

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]
        cut = 1

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

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

[tian-pengfei]

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {

           int re=0;
            //按照起点进行排序
            //两个两个进行比较，当两个冲突时必须移除某一个区间的时候，应该移除应该最大限度减少冲突的的区间。
            //也就是说，当两个冲突的时候，选择末尾最小,才能对后面的区间冲突影响最小。

            sort(intervals.begin(),intervals.end(),[](const auto& a,const auto& b){
                return a[0]<b[0];
            });

            for(int i =0 ,j=i+1;j<intervals.size();){

//                检测两个区间是否冲突
                if(intervals[i][1]>intervals[j][0]){
                    //说明冲突
                    //留下末尾较小的
                    if(intervals[i][1]<=intervals[j][1]){
                        //i还需要和下一个比较看是否冲突
                        j++;
                    }else{
                        //i后面两个接着进行比较
                        i=j++;
                    }
                    re++;

                }else{
                    //不冲突就后面两个进行比较
                    i=j++;
                }

            }

            return re;

    }
};

[ZJP1483469269]

class Solution:
    def eraseOverlapIntervals(self, ls: List[List[int]]) -> int:
        ls = sorted(ls , key = lambda x : x[1])
        end = -1e9
        res = 0
        for s , e in ls:
            if s < end:
                res += 1
            else:
                end = e
        return res

[ZhiweiZhen]

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]
        remove = 1

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

        return n - remove

贪心算法 T complexity : nlogn S complexity: nlogn

[li65943930]

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)

[hulichao]

思路

// 思路,按左边界或者右边界排序，右边界升序，按顺序寻找右边界最小的且不与前面已选边界重叠的， // 记下有多少个不互相重叠的区间，总数减去它即可 // 为什么是这样呢？局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间 此题卡壳的点就是局部最优为什么是全局最优

代码

class Solution {

    // 思路,按左边界或者右边界排序，右边界升序，按顺序寻找右边界最小的且不与前面已选边界重叠的，
    // 记下有多少个不互相重叠的区间，总数减去它即可
    // 为什么是这样呢？局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间
    // case 
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length < 2) return 0;

        Arrays.sort(intervals, (x, y) -> {
            if (x[1] != y[1])
                return x[1] - y[1];
            else 
                return y[0] - x[0];
        });

        int count = 1;
        int edge = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (edge <= intervals[i][0]){
                count ++; //non overlap + 1
                edge = intervals[i][1];
            }
        }
        return intervals.length - count;
    }
}

复杂度分析

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

[cszys888]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key = lambda x: x[0])
        start, end = intervals[0][0], intervals[0][1]
        result = 0
        for interval in intervals[1:]:
            if interval[0] >= end:
                start = interval[0]
                end = interval[1]
            else:
                result += 1
                end = min(end, interval[1])
        return result

time complexity: O(nlogn) space complexity: O(logn)

[yijing-wu]

// Greedy --- 可以将问题转换成求最大的无重叠区间个数
// TC = O(NlogN), sort takes O(NlogN)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // sort the intervals, time: O(NlogN)
        // 以end进行排序，从小到大
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int len = intervals.length;
        int right = intervals[0][1];
        int count = 1;
        // iterate the intervals, time: O(N)
        for(int i = 1; i < len; ++i)  {
            if(intervals[i][0] >= right) {
                count++;
                right = intervals[i][1];
            }
        }
        return len - count;
    }
}

[ZacheryCao]

Idea

Sort + Binary Search + Greedy

Code:

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()<2) return 0;
        sort(intervals.begin(), intervals.end());
        return intervals.size()-LIS(intervals);
    }

    int LIS(vector<vector<int>>& intervals){
        vector<int> d;
        vector<int>::iterator up;
        for(int i = 0; i < intervals.size(); i++){
            up = upper_bound(d.begin(), d.end(), intervals[i][1]);
            if(up!=d.end()) d[up-d.begin()] = intervals[i][1];
            else if(d.size()==0 or d.back()<=intervals[i][0]) d.push_back(intervals[i][1]);
        }
        return d.size();
    }
};

Complexity:

Time: O(N log N) Space: O(N)

[zhiyuanpeng]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        dp = [1] * len(intervals)
        ans = 1
        for i in range(1, 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)
                    ans = max(ans, dp[i])
                    break
        return len(intervals) - ans

[falconruo]

思路:

排序 + 贪心

复杂度分析:

• 时间复杂度: O(NlogN)，N为区间数组intervals的长度
• 空间复杂度: O(logN)

代码(C++):

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

        if (n == 0) return 0;

        sort(intervals.begin(), intervals.end()); // O(NlogN), O(logN)

        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] < intervals[last][1]) { // overlapped
                ++res;
                if (intervals[i][1] < intervals[last][1])
                    last = i;
            } else
                last = i;
        }

        return res;
    }
};

[Tesla-1i]

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]
        cut = 1

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

[1149004121]

435. 无重叠区间

思路

贪心算法。被留下的区间end应该尽量小才能塞下最多。

代码

var eraseOverlapIntervals = function(intervals) {
    const n  = intervals.length;
    let cnt = 0;
    intervals.sort((a, b) => a[1] - b[1]);
    let end = intervals[0][1];
    for(let i = 1; i < n; i++){
        if(intervals[i][0] < end){
            cnt++;
        }else{
            end = intervals[i][1];
        }
    };
    return cnt;
};

复杂度分析

• 时间复杂度：O(NlogN)。
• 空间复杂度：O(1)。

[Bochengwan]

思路

通过start point来进行heap排序，如果无重叠，count+1.

代码

import heapq as hp
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        rec = []
        for interval in intervals:
            rec.append((interval[0],interval[1]))
        hp.heapify(rec)
        ans = 0
        last = float('-inf')

        for _ in range(len(rec)):
            (a,b) = hp.heappop(rec)
            if last>a:
                if last>b:
                    last = b
                ans+=1
                continue
            last = b
        return ans

复杂度分析

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

[KennethAlgol]

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) return 0;
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int count = 1;
        int[] interval = intervals[0];

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

[Toms-BigData]

func eraseOverlapIntervals(intervals [][]int)  int {
    n:= len(intervals)
    if n == 0{
        return 0
    }
    sort.Slice(intervals, func(i, j int) bool {return intervals[i][1]<intervals[j][1]})
    ans:=1
    right:= intervals[0][1]
    for i := 1; i < n; i++ {
        if intervals[i][0]>=right{
            ans++
            right = intervals[i][1]
        }
    }
    return n-ans
}

[tongxw]

思路

贪心或者LIS 贪心的想法是按区间末尾排序，尽量给右侧留距离

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (t1, t2) -> (t1[1] - t2[1]));
        int n = intervals.length;
        int totalNonOverlapping = 1;
        int rightMost = intervals[0][1];
        for (int i=1; i<n; i++) {
            if (intervals[i][0] >= rightMost) {
                // new non-overlaping interval
                totalNonOverlapping++;
                rightMost = intervals[i][1];
            }
        }

        return n - totalNonOverlapping;
    }
}

TC: O(nlogn) SC: O(1)

[chakochako]

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:
                ans += 1
                right = intervals[i][1]

        return n - ans

[moirobinzhang]

Code:

public int EraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.Length == 0)
            return 0;

        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        int[] dp = new int[intervals.Length];
        int maxLen = 1;

        for (int i = 0; i < intervals.Length; i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (intervals[i][0] >= intervals[j][1])
                {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                    break;
                }

            }

            dp[i] = Math.Max(dp[i], 1);
            maxLen = Math.Max(maxLen, dp[i]);
        }

        return intervals.Length - maxLen;
}

[yan0327]

func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    sort.Slice(intervals,func(i,j int)bool{
        return intervals[i][1] < intervals[j][1]
    })
    if len(intervals) == 0{
        return 0
    }
    maxRemain := 1
    curRight := intervals[0][1]
    for i:=1;i<n;i++{
        if intervals[i][0] >= curRight{
            curRight = intervals[i][1]
            maxRemain++
        }
    }
    return n-maxRemain
}

[z1ggy-o]

思路

类似的题目还有 56 合并区间

套路都是在排序之后对比区间值，进行相应的贪心操作。

代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });

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

复杂度分析

• 时间：O(nlogn)
• 空间：O(1)

[charlestang]

思路

贪心

把所有区间按照右端点排序，选择最左边一个。然后继续选择与此不重叠的最右侧区间。直到扫描过所有的区间。

就能构成最多的区间重叠。

代码

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key= lambda x: x[1])
        r = intervals[0][1]
        ans = 1

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

时间复杂度 O(nlogn)

空间复杂度 O(logn)

[zjsuper]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if n == 0: return 0
        intervals.sort(key = lambda x:x[1])
        #print(intervals)
        count = 0
        r  = intervals[0][1]
        for i in range(1,n):

            if r > intervals[i][0]:
                count += 1
            else:
                r  = intervals[i][1]
        return count

[haixiaolu]

思路

排序 + 贪心

• sort by the start point

• compare the start points

  • if the start points are the same,

    • then compare the end point of the first interval and the start of the second interval
    • if the start of the second interval is smaller than the end of the first interval
    • we have an overlap

      代码 / python

      
      class Solution:
      def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
      intervals.sort()

    res = 0 prevEnd = intervals[0][1] for start, end in intervals[1:]: if start >= prevEnd: prevEnd = end else: res += 1 prevEnd = min(end, prevEnd) return res

## 复杂度分析
- 时间复杂度： O(n log n)
- 空间复杂度： O(1)

[hx-code]

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

[LannyX]

思路

贪心

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        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 res = 1;
        for(int i = 1; i < n; i++){
            if(intervals[i][0] >= right){
                res++;
                right = intervals[i][1];
            }
        }
        return n - res;
    }
}

复杂度分析

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

[jiaqiliu37]

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

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

        return n - cnt

Time complexity O(n) Space complexity O(n) or O(log n) depending on the sorting method

[zol013]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x:x[1])
        count = 1
        right = intervals[0][1]

        for interval in intervals:
            if right <= interval[0]:
                count += 1
                right = interval[1]

        return len(intervals) - count

[wenlong201807]

代码块

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

  let count = 1
  let end = intervals[0][1]

  for (let i = 1; i < intervals.length; i++) {
    let interval = intervals[i]
    if (interval[0] >= end) {
      end = interval[1]
      count += 1
    }
  }

  return intervals.length - count
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[CoreJa]

思路

这个题太有意思了，今天再回顾一下他作为LIS的dp做法和二分做法(LIS候选人)，以及他最好用的贪心法。首先记得反向思考，本质是取尽可能长的不重叠区间再拿总长度去减。

• 类LIS的DP：状态转移方程：$123$，复杂度$O(n^2)$，py跑直接TLE，看LC题解意思是别的语言可能不会TLE
• 类LIS的贪心+二分优化：也是LC:300的做法，设置ans数组表示LIS候选人，ans[i]指长度为i的LIS末尾的元素，复杂度$O(n\log n)$
• 区间贪心法：不考虑排序的情况只需要一次遍历即可。将所有区间按右界排序，维护一个cur表示当前最长不重叠区间的右区间，遍历时用intervals[i]的start去和cur比较，如果start>=cur，则intervals[i]对区间长度有贡献，计数+1，cur改为当前intervals[i]的end，复杂度$O(n\log n)$
  • 右界排序的理解：这个题目的区间贪心，贪的是使区间数最多，按照右界排序，可以让右界小的先被选中，保证剩下的空间尽可能的大。类似的还有LC: 452，贪的是尽量让区间重叠，左界和右界排序可以按顺序找到和这个区间重叠的所有区间。只能左界排序的也可以参考LC: 253去对比理解。

代码

class Solution:
    # 类LIS的DP：状态转移方程：$123$，复杂度$O(n^2)$，py跑直接TLE，看LC题解意思是别的语言可能不会TLE
    def eraseOverlapIntervals1(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if intervals[i][0] >= intervals[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return n - max(dp)

    # 类LIS的贪心+二分优化：也是LC:300的做法，设置`ans`数组表示**LIS候选人**，`ans[i]`指长度为`i`的LIS末尾的元素，
    # 复杂度$O(n\log n)$
    def eraseOverlapIntervals2(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        ans = [intervals[0]]
        for i in range(1, n):
            if intervals[i][0] >= ans[-1][1]:
                ans.append(intervals[i])
            else:
                left, right = 0, len(ans)
                while left < right:
                    mid = (left + right) // 2
                    if intervals[i][1] < ans[mid][1]:
                        right = mid
                    else:
                        left = mid + 1
                if left != len(ans):
                    ans[left] = intervals[i]
        return n - len(ans)

    # 区间贪心法：不考虑排序的情况只需要一次遍历即可。将所有区间按右界排序，维护一个`cur`表示当前最长不重叠区间的右区间，遍历
    # 时用`intervals[i]`的`start`去和`cur`比较，如果`start`>=`cur`，则`intervals[i]`对区间长度有贡献，计数+1，cur改为
    # 当前`intervals[i]`的`end`，复杂度$O(n\log n)$
    # - 右界排序的理解：这个题目的区间贪心，贪的是使区间数最多，按照右界排序，可以让右界小的先被选中，保证剩下的空间尽可能的
    # 大。可以参考LC: 253对比左界排序的理解。
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = 1
        cur = intervals[0][1]
        for start, end in intervals[1:]:
            if start >= cur:
                ans += 1
                cur = end
        return len(intervals) - ans

[Myleswork]

思路一：DP（LIS）

将intervals依据start排序后，找出start～end的最长非严格递增子序列，总长度减去LIS长度即为需要删去的区间数

代码

class Solution {
public:
    int LIS(vector<vector<int>>& intervals){
        int len = intervals.size();
        vector<int> dp(len,1);
        for(int i = 1;i<len;i++){
            for(int j = i-1;j>=0;j--){
                if(intervals[j][1]<=intervals[i][0]){
                    dp[i] = max(dp[j]+1,dp[i]);
                    break;
                }
            }
        }
        int res = 0;
        for(int i=0;i<len;i++){
            res = max(res,dp[i]);
        }
        return res;
    }

    static bool cmp(vector<int>& a,vector<int>& b){
        if(a[0]!=b[0]) return a[0]<b[0];
        else return a[1]<b[1]; 
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int size = intervals.size();
        sort(intervals.begin(),intervals.end(),cmp);
        return size-LIS(intervals);
    }
};

复杂度分析 时间复杂度：O(n^2) 空间复杂度：O(n)

[alongchong]

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[0] - interval2[0];
            }
        });

        int n = intervals.length;
        int[] f = new int[n];
        Arrays.fill(f, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (intervals[j][1] <= intervals[i][0]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
        }
        return n - Arrays.stream(f).max().getAsInt();
    }
}

[xuhzyy]

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        intervals.sort(key=lambda x: x[1])
        cnt, end = 1, intervals[0][1]
        for i in range(1, len(intervals)):
            if end <= intervals[i][0]:
                cnt += 1
                end = intervals[i][1]
        return len(intervals) - cnt

[callmeerika]

思路

贪心

代码

var eraseOverlapIntervals = function (intervals) {
    if (!intervals.length) return 0;
    intervals.sort((v1, v2) => v1[1] - v2[1]);
    let n = intervals.length;
    let right = intervals[0][1];
    let res = 1;
    for (let vv of intervals) {
      if (vv[0] >= right) {
        res++;
        right = vv[1];
      }
    }
    return n - res;
  };

复杂度

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

[stackvoid]

思路

贪心 答案

代码

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

算法分析

Time O(nlogn) Space O(n)

[biscuit279]

思路

寻找右端最小的区间

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])
        n = len(intervals)
        right = intervals[0][1]
        ans = 1
        for i in range(1,n):
            if intervals[i][0] >= right:
                ans += 1
                right = intervals[i][1]
        return n - ans

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

[xinhaoyi]

class Solution { public int eraseOverlapIntervals(int[][] intervals) { //1.先将每个区间按照区间终点大小排序 //2.对排序之后的区间进行比较，如果存在重叠关系，则计数加一 //判断数组是否为空 if(intervals.length==0){ return 0; } //对数组进行排序，根据区间结尾的大小 Arrays.sort(intervals,new Comparator<int[]>(){ //对数组进行排序 public int compare(int[] o1, int[] o2) { return o1[1]-o2[1]; } }); //区间之间进行比较，将重叠的区间移除(n+1) int total = 0; int prev = intervals[0][1];//第一个区间的结尾 for(int i =1;i<intervals.length;i++){ if(prev>intervals[i][0]){ total++; }else{ prev = intervals[i][1]; } } return total; } }

[biaohuazhou]

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

[CodingProgrammer]

思路1

动态规划

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            throw new IllegalArgumentException();
        }
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        int n = intervals.length;
        // dp[i] 表示以底 i 个区间结尾最多能合并的区间个数
        // 只要后一个区间的开始位置小于前一个区间的结束位置，那么这两个区间就可以合并
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (intervals[i][0] >= intervals[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    res = Math.max(res, dp[i]);
                    break;
                }
            }
        }
        return n - res;
    }
}

复杂度

• 时间复杂度： O(N^2)
• 空间复杂度：O(N)

思路2

贪心

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            throw new IllegalArgumentException();
        }
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        // 先求最多能够合并的区间
        int n = intervals.length;
        int end = intervals[0][1], res = 0;
        for (int i = 1; i < n; i++) {
            // 如果后一个区间的头小于前一个区间的尾说明两个区间有重叠必须移除一个
            if (intervals[i][0] < end) {
                res++;
                end = Math.min(end, intervals[i][1]); // 为了防止在下一个区间和现有区间有重叠，我们应该让现有区间越短越好，所以应该移除尾部比较大的，保留尾部比较小的。
            } else {
                end = intervals[i][1];
            }

        }
        return res;
    }
}

复杂度

• 时间复杂度：O(NlogN)
• 空间复杂度：O(logN)

[Aobasyp]

思路 贪心 + 二分

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)

[GaoMinghao]

思路

将题目转化为做多的无重叠子数组，然后用贪心算法

daima

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] != o2[1])
                    return o1[1] - o2[1];
                else
                    return o1[0] - o2[0];
            }
        });
        int count = 1, end = intervals[0][1];
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] >= end) {
                count++;
                end = intervals[i][1];
            }
        }
        return intervals.length-count;
    }
}

时间复杂度

O(nlogn) -> 排序的开销

[hdyhdy]

func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    if n == 0 {
        return 0
    }
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if intervals[j][1] <= intervals[i][0] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    return n - max(dp...)
}

func max(a ...int) int {
    res := a[0]
    for _, v := range a[1:] {
        if v > res {
            res = v
        }
    }
    return res
}

[dahaiyidi]

Problem

[435. 无重叠区间](https://leetcode-cn.com/problems/non-overlapping-intervals/)

++

难度中等604

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

---

Note

• 按照区间右端点降序排列，统计不重叠区间的数量。
• python：排序的写法intervals.sort(key=lambda x: x[1])
• C++：注意排序的写法：
  • sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v){ return u[1] < v[1]; });

---

Complexity

• 时间O：nlogn 排序
• 空间O：logn 排序

---

Python

C++

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int num = 0; // 统计不重叠区间的数量
        // 按照区间右端点降序排列
        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v){
            return u[1] < v[1];
        });
        int right = INT_MIN;
        for(int i = 0; i < intervals.size(); i++){
            if(intervals[i][0] >= right){
                num++;
                right = intervals[i][1];
            }
        }
        return intervals.size() - num;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[guangsizhongbin]

func eraseOverlapIntervals(intervals [][]int) int { // 本身为空，需要移除0个 n := len(intervals) if n == 0{ return 0 }

// 根据第二维进行排序， 从小到大
sort.Slice(intervals, func(i, j int) bool{ return intervals[i][1] < intervals[j][1]})
ans, right := 1, intervals[0][1]
for _, p := range intervals[1:]{
    if p[0] >= right {
        ans++
        right = p[1]
    }
}
return n - ans

}

[declan92]

思路
区间按照起始位置排序+剩余区间不重叠==>剩余区间不严格递增==>求最长递增(不严格)子序列

1. dp(i)包含nums[i]元素的最长递增子序列长度;
2. dp(i) = dp(j) +1;j<i&&nums[j][1]<=nums[i][0],且因为有序,j离i最近;
3. dp(i) = 1;
4. 顺序遍历
5. 注意结果求移除区间最小数量
   java code

   class Solution {
   public int eraseOverlapIntervals(int[][] intervals) {
       int n = intervals.length;
       if (n == 0) return 0;
       Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
       int[] dp = new int[n];
       Arrays.fill(dp, 1);
       int ans = 1;
       for(int i = 1;i<n;i++){
           for(int j = i-1;j>=0;j--){
               if(intervals[i][0]>=intervals[j][1]){
                   dp[i] = Math.max(dp[i], dp[j]+1);
                   ans = Math.max(ans, dp[i]);
                   break;
               }
           }
       }
       return n-ans;
   }
   }

   时间:O(n^2)
   空间O(n)

[Hacker90]

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

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

    int n = intervals.size();
    vector<int> f(n, 1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (intervals[j][1] <= intervals[i][0]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    return n - *max_element(f.begin(), f.end());
}

};

[shamworld]

var eraseOverlapIntervals = function(intervals) {
    let len = intervals.length;
    if(len==0) return 0;
    //通过区间最后一个元素排序
    intervals.sort((a,b)=>a[1]-b[1]);
    //最多不重叠区间数，至少为1
    let count = 1;
    //初始结尾
    let end= intervals[0][1];
    for(let inter of intervals){
        let num = inter[0];
        if(num>=end){
            count++;
            end = inter[1];
        }

    }
    return len-count;
};

[demo410]

public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        if (n == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;
        for(int i = 1;i<n;i++){
            for(int j = i-1;j>=0;j--){
                if(intervals[i][0]>=intervals[j][1]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    ans = Math.max(ans, dp[i]);
                    break;
                }
            }
        }
        return n-ans;
    }

[WANGDI-1291]

代码

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)

[rzhao010]

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
        int pre = intervals[0][1];
        int remove = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < pre) {
                remove++;
                pre = Math.min(pre, intervals[i][1]);
            } else {
                pre = intervals[i][1];
            }
        }
        return remove;
    }

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