【Day 66 】2022-06-05 - 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

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

[Ellie-Wu05]

思路：贪心

1. 我们可以用贪婪来解决问题。
2. 按每个元素的结束值对给定的输入列表进行排序。
3. 我们设置了一个左边的边界，现在我们只需要比较当前开始和以前的结束。如果当前开始大于或等于前一个结束。然后没有重叠，我们将左侧边界更新到当前末尾并继续迭代。
4. 否则，重叠，那么我们需要将1增加到删除的数量。

代码

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

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

        cnt = 0
        first_end = intervals[0][1]

        for i in range(1,len(intervals)):
            curr = intervals[i]
            if curr[0] >= first_end:
                first_end = curr[1]
            else:
                cnt+=1

        return cnt

复杂度

时间：Onlogn因为使用了sort 空间：O1

[MichaelXi3]

Idea

本题要求我们去找出 remove 几个 intervals 才能达成 Longest Non-overlapping Intervals，也就是说我们要找到 Longest Non-overlapping Intervals 的长度！

1. 首先，我们需要基于 intervals 的 end 大小进行 sorting，我们需要这个 non-overlapping interval 的第一个 interval 的 end 越小越好，因为这样才能让第二个 interval 的 start 有更多可能性
2. Coding难点：要记得怎么写 comparator class 并 declare
3. 然后，我们历遍 sorting 之后的 intervals，试图去搭建一个 Longest Non-overlapping Intervals 并实时记录其长度。于是我们就得到了一个最长可能的 Non-overlapping Intervals。

   Code

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

    // Sort the intervals based on the first number size
    Comparator<int[]> c = new comparator();
    Arrays.sort(intervals, c);

    // Find the longest Non-overlapping Intervals
    int end = intervals[0][1];
    int size = 1;
    for (int i=1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            size++;
            end = intervals[i][1];
        }
    }

    // Calculate the num of intervals need to be removed
    return intervals.length - size;
}

public class comparator implements Comparator<int[]> {
    public int compare (int[] a, int[] b) {
        // Sort from smallest to biggest
        return a[1] - b[1];
    }
}

}

# Complexity
- Time: O(nlog(n)) → Sorting
- Space: O(n)

[Yongxi-Zhou]

思路

greedy, remove the bigger one because it has more possibility to overlap with other intervals.

代码

    class Solution(object):
        def eraseOverlapIntervals(self, intervals):
            """
            :type intervals: List[List[int]]
            :rtype: int
            """
            intervals.sort(key = lambda x: [x[0], x[1]])
            preEnd = intervals[0][1]
            res = 0
            for i in range(1, len(intervals)):
    #             [1, 2] [2, 3] not overlapping
                if intervals[i][0] < preEnd:
                    res += 1
                    preEnd = min(intervals[i][1], preEnd)
                else:
                    preEnd = intervals[i][1]
            return res

复杂度

time O(NlogN) sorting space O(1)

[ZacheryCao]

Idea

Greedy + Binary Search

Code

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if not n:
            return n
        intervals.sort()
        d = []
        for s, e in intervals:
            i = bisect.bisect_left(d, e)
            if i < len(d):
                d[i] = e
            elif not d or d[-1]<=s:
                d.append(e)
        return n-len(d)

[JiangWenqi]

cpp

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

        sort(intervals.begin(), intervals.end(), [](auto &a, auto &b)
             { return a[1] < b[1]; });
        int end = intervals[0][1], res = 0;
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] < end)
                res++;
            else
                end = intervals[i][1];
        }
        return res;
    }
};

[MoonLee001]

思路

贪心，排序

代码

var solution = function(nums) {
  nums.sort((a, b) => a[1] - b[1]);
  const n = nums.length;
  let lastPos = nums[0][1];
  let ans = 1;

  for (let i = 1; i < n; i++) {
    const cur = nums[i];
    if (lastPos <= cur[0]) {
      ans++;
      lastPos = cur[1];
    }
  }

  return n - ans;
}

复杂度分析

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

[djd28176]

class Solution {
    class myComparator implements Comparator<int[]>{
        public int compare(int[] a, int[] b){
            return a[1] - b[1];
        }
    }

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new myComparator());
        int end = intervals[0][1], prev = 0, count = 0;

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

}

[houmk1212]

思路

贪心，每次只找右端点最小的，并且不重叠的

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });

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

复杂度

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

[carterrr]

public int eraseOverlapIntervals(int[][] intervals) { if(intervals.length == 0) return 0; Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));// 保证一直取到最小右边界 剩下的可能取到的区间会更多 int res = 0; for (int i = 1, cur = intervals[0][1]; i < intervals.length; i++) { if(intervals[i][0] < cur ) { res ++; // 去掉无效的区间 continue; } if(intervals[i][1] >cur) cur = intervals[i][1]; // 或者更新右边界

    }
    return res;
}

[Magua-hub]

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

    }
};

[xingchen77]

        if len(intervals) == 0:
            return 0
        intervals.sort(key = lambda i:i[1])
        end = intervals[0][1]
        cnt =  1
        for i in range(1, len(intervals)):
            if intervals[i][0] >= end:
                end = intervals[i][1]
                cnt += 1
        return len(intervals) - cnt

[VictorHuang99]

贪心算法

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a,b) => a[0] - b[0]); // 升序排序
    let pre = intervals[0][1]; 
    let res = 0;
    for (let i=1; i<intervals.length; i++) {
        if (intervals[i][0] >= pre) { // 当相邻区间不重合，保留当前区间；
            pre = intervals[i][1];
        } else { // 当区间重合，保留二者中右边界较小者。
            res += 1;
            pre = Math.min(pre, intervals[i][1]);
        }
    }
    return res;
};

[hyh331]

Day66 思路

1. 先将区间按照右端点从小到大排序
2. 以首个区间右端点为开始，依次比较下一个端点左侧>=这个端点右侧，若大于则将区间右移至此区间右侧。ans+1 3.最后需要移除的就是n-ans（ans为互补重叠的区间数）

   class Solution {
   public:
   int eraseOverlapIntervals(vector<vector<int>>& intervals) {
       if(intervals.empty()){
           return 0;
       }
       //bool cmp(vector<int>& u, vector<int>& v){
       //    return u[1] < v[1];
       //}
       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){
               right=intervals[i][1];
               ans +=1;
           }
       }
       return n-ans;
   }
   };

   复杂度分析

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

[KWDFW]

Day66

435、无重叠区间

javascript #贪心算法

思路

1、按照右边界升序排序数组

2、选择保留右边界小的数组，让移除区间尽可能大，使得移除区间个数减少

3、找到右边界的小的数组之后，去找该区间结束的下一个数组，即n[0]>=end，并记录count

4、返回length - count 得到移除区间最小数

代码

var eraseOverlapIntervals = function(intervals) {
  intervals.sort((a, b) => {
    return a[1] - b[1];
  })
  //按照右边界升序排序
  let count = 1;//剩余空间的数量
  end = intervals[0][1];//当前空间的右边界
  for (let n of intervals) {//遍历数组
    if (n[0] >= end) {//左边界大于上次的右边界
      end = n[1];//修改上次右边界
      count++;//记录剩余空间的数量
    }
  }
  return intervals.length - count;
  //返回移除区间的最小数量
};

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(logn)

[currybeefer]

static bool compare(vector& a, vector& b) { if(a[0] == b[0]) return a[1] < b[1]; else return a[0] < b[0]; }

int eraseOverlapIntervals(vector<vector<int>>& arr) {

    int n = arr.size();

    sort(arr.begin(), arr.end(), compare);

    int count = 0;

    int prev_start = arr[0][0];

    int prev_end = arr[0][1];

    for(int i = 1; i < n; i++)
    {
        int curr_start = arr[i][0];

        int curr_end = arr[i][1];

        if(curr_start < prev_end)    // overlaping condition
        {
            count++;

            // delete the interval which has higher end value

            prev_end = min(prev_end, curr_end);
        }
        else    // non-overlaping condition
        {
            prev_start = arr[i][0];

            prev_end = arr[i][1];
        }
    }

    return count;

[xil324]

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        intervals = sorted(intervals, key = lambda x: x[1]); 
        count = 1; 
        curr_end = intervals[0][1]; 
        for i in range(1, len(intervals)): 
            if intervals[i][0] >= curr_end:
                count+=1;
                curr_end = intervals[i][1]; 
        return len(intervals) - count; 

[antmUp]

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)

[xiayuhui231]

题目

无重叠区间

代码

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

复杂度

时间复杂度:O(nlogn) 空间复杂度:O(1)

[miss1]

思路

先将intervals按end排序。最终的intervals是一个递增的序列，排序后end已经就位，只要把start小于前一个end的数去掉就行

代码

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

复杂度

• time: O(nlogn)
• space: O(n)

[freedom0123]

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

         int e = intervals[0][1] ;
         int n = intervals.length ;
         int cnt = 0 ;
         for (int i = 1 ; i < n ; ++i) {
             if (e > intervals[i][0]) {
                 cnt++;
             } else {
                 e = intervals[i][1] ;
             }
         }
         return cnt ;        
    }
}

[XXjo]

var eraseOverlapIntervals = function(intervals) {
    intervals = intervals.sort((a, b) => a[1] - b[1]);
    let res = 0;
    let index = 0;
    let flag;
    flag = intervals[0][1];
    while(index < intervals.length - 1){
        if(intervals[index + 1][0] < flag){
            res++;
        }
        else{
            flag = intervals[index + 1][1];
        }
        index++;
    }
    return res;
};

[okbug]

JS

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

  let end = intervals[0][1], res = intervals.length - 1;

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

  return res;
};

[Geek-LX]

6.5

思路：贪心

代码：

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)

[Orangejuz]

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

        return res

[revisegoal]

贪心

• 转换为求最长连续不重叠区间长度len，答案则是n - len
• 通过舍弃合适区间避免重叠，按右端点顺序排序才能得到最长，按左端点在有两个左端点相同区间情况下不一定选择到最适合的区间舍弃

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        if (n == 0) {
            return 0;
        }
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int right = intervals[0][1];
        int len = 1;
        for (int i = 1; i < n; i++) {
            if (right <= intervals[i][0]) {
                len++;
                right = intervals[i][1];
            }
        }
        return n - len;
    }
}

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

[ShuqianYang]

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

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

        cnt = 0
        first_end = intervals[0][1]

        for i in range(1,len(intervals)):
            curr = intervals[i]
            if curr[0] >= first_end:
                first_end = curr[1]
            else:
                cnt+=1

        return cnt

[LQyt2012]

思路

贪心算法

代码

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

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

[taojin1992]

class Solution {
    // |. |
    //.  |. |
    // time: O(nlogn), n = intervals.length
    // space: O(1)
    public int eraseOverlapIntervals(int[][] intervals) {
        // sort by starting time
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
        int cur = 0;
        int rmNum = 0;
        for (int next = 1; next < intervals.length; next++) {
            if (intervals[next][0] < intervals[cur][1]) { // need to rm
                rmNum++;
                // which one to rm
                // rm one with larger end
                if (intervals[next][1] < intervals[cur][1]) {
                    // rm cur
                    cur = next;
                } // else, rm next, continue
            }
            else {
                cur = next;
            }
        }
        return rmNum;
    }
}

[asuka1h]

class Solution { public: int eraseOverlapIntervals(vector<vector>& intervals) { sort(intervals.begin(), intervals.end(), [](vector&l, vector&r){ / if(l[1] < r[1]){ return true; } else{ return false; }/ return l[1] < r[1]; }); int cnt = 0; int curr = INT_MIN; for(auto i: intervals){

        if(i[0] < curr){
            cnt++;
        }
        else{
            curr = i[1];
        }
    }
    return cnt;
}

};

时间复杂度:

O(nlogn)

[mo660]

class Solution {
public:
    static bool cmp(vector<int>&a, vector<int>&b)
    {
        return a[1]<b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(),cmp);
        int count = 0, cur = INT32_MIN;;
        for (auto a:intervals)
        {
            int l = a[0], r = a[1];
            if (l < cur){
                count++;
            }else{
                cur = r;
            }
        }
        return count;
    }
};

[wychmod]

思路

贪心，评论区看见个兄弟的思路，太牛了，直接end排序，On 统计不交叉的区间，然后总数减去这个就是要删除的。

代码

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 1:
            return 0
        intervals = sorted(intervals, key=lambda a:a[1])
        count = 1
        end = intervals[0][1]
        for i in range(1, len(intervals)):
            if end <= intervals[i][0]:
                count += 1
                end = intervals[i][1]
        return len(intervals) - count

复杂度分析

时间复杂度Onlogn 空间复杂度O1

[bzlff]

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)

[linjunhe]

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        return n - intervalSchedule(intervals);
    }

    // 区间调度算法，算出 intvs 中最多有几个互不相交的区间
    int intervalSchedule(int[][] intvs) {
        if (intvs.length == 0) return 0;
        // 按 end 升序排序
        Arrays.sort(intvs, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[1] - b[1];
            }
        });
        // 至少有一个区间不相交
        int count = 1;
        // 排序后，第一个区间就是 x
        int x_end = intvs[0][1];
        for (int[] interval : intvs) {
            int start = interval[0];
            if (start >= x_end) {
                // 找到下一个选择的区间了
                count++;
                x_end = interval[1];
            }
        }
        return count;
    }
}

[maggiexie00]

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

[flyzenr]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 0: return 0
        intervals.sort(key=lambda x: x[1])
        count = 1 # 记录非交叉区间的个数
        end = intervals[0][1] # 记录区间分割点
        for i in range(1, len(intervals)):
            if end <= intervals[i][0]:
                count += 1
                end = intervals[i][1]
        return len(intervals) - count

[houyanlu]

思路

要找到最大不重叠区间的个数， 我们把本题的区间看成是会议，那么按照右端点排序，我们一定能够找到一个最先结束的会议 能够预定的最大的会议数量是多少？

代码

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

        int count = 1; // 非重复区间的个数
        int curEnd = intervals[0][1];
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals[i][0] >= curEnd) {
                count++;
                curEnd = intervals[i][1];
            }
        }

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

复杂度分析

• 时间复杂度：O(n + 排序时间)
• 空间复杂度：排序所占空间

[zhiyuanpeng]

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 r <= intervals[i][0]:
                ans += 1
                r = intervals[i][1]
        return len(intervals) - ans

time O(nlogn) space O(n)

[ShawYuan97]

思路

首先按照左区间进行排序，然后逐个确定右边的区间 （核心思想，保证每个区间之间尽可能紧密） 保证了左区间是有序的，然后维护一个end（表示当前区间的末尾），寻找下一个左区间大于end的区间；
如果左区间大于等于end，那么不需要删掉该区间，修改end；
如果右区间小于end，那么需要删掉前一个区间，修改end； 如果左区间小于end，需要删掉该区间。

关键点

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        """
        移除区间，使之互不重叠

        """
        intervals.sort(key=lambda x:x[0])
        count = -1
        start,end = intervals[0]
        for interval in intervals:
            if interval[1] < end:
                end = interval[1]
                count += 1
            elif interval[0] < end:
                count += 1
            else:
                end = interval[1]
        return count

复杂度分析

令 n 为数组长度。

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

[zhishinaigai]

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int len=intervals.size();
        if(len==0)
        return 0;
        sort(intervals.begin(),intervals.end());
        int l=intervals[0][0];
        int r=intervals[0][1];
        int n=0;
        for(int i=1;i<len;i++){
            if(intervals[i][0]==l){
                n++;
                r=min(r,intervals[i][1]);
            }
            else{
                if(intervals[i][0]<r){
                    n++;
                    r=min(r,intervals[i][1]);
                }
                else{
                    l=intervals[i][0];
                    r=intervals[i][1];
                }
            }
        }
        return n;
    }

[tensorstart]

//leetcode执行超时 复杂度过高
var eraseOverlapIntervals = function (intervals) {
    if (!intervals.length) {
        return 0;
    }

    intervals.sort((a, b) => a[0] - b[0]); //按左边界排序
    const n = intervals.length;
    const dp = new Array(n).fill(1); //初始化dp数组

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            //循环i,j找出intervals中最多有多少个不重复的区间
            //j的右边界小于i的左边界 相当于多出了一个不重合区间
            if (intervals[j][1] <= intervals[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1); //更新dp[i]
            }
        }
    }
    return n - Math.max(...dp); //n减去最多的不重复的区间 就是最少删除区间的个数
};