【Day 66 】2021-11-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

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

[yanglr]

思路:

贪心法。

题目要求的是移除区间的最小数量, 我们可以逆向思考: 最多留下几个区间(将最多留下的区间数量记作maxRemain), 将区间总数记作N, 那么 N - maxRemain 即为所求。

步骤: ①按区间右端点进行从小到大排序 ②遍历: 从左到右遍历每个区间

能选则选: 如果当前区间与它相邻的前一个区间没有交集，就选上

这样选出来的就一定是最优解, 要证明用反证法, 过程就不写了。

代码:

实现语言: C++

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& R) { /* R: 代表ranges */
        auto cmp = [](const vector<int>& p1, const vector<int>& p2)
        {
            return p1[1] < p2[1];
        };
        sort(R.begin(), R.end(), cmp);
        const int len = R.size();
        if (R.empty()) return 0;
        int maxRemain = 1; // maxRemain: 最多保留下来多少个区间
        int curRight = R[0][1];
        for (int i = 1; i < len; i++)
        {
            if (R[i][0] >= curRight) /* 新来的区间的左边界R[i][0] 与当前区间的右边界比较, 如果≥成立说明可以再留下1个新的区间 */
            {
                maxRemain++;
                curRight = R[i][1];
            }
        }    
        return len - maxRemain;
    }
};

复杂度分析:

• 时间复杂度: O(N logN), 用到了排序
• 空间复杂度: O(1)

[Tao-Mao]

Idea

greedy algorithm

class Solution {
  class myComparator implements Comparator<int[]> {
    public int compare(int[] a, int[] b) {
      return a[1] - b[1];
    }
  }
  public boolean isOverlapping(int[] i, int[] j) {
    return i[1] > j[0];
  }
  public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
      return 0;
    }
    Arrays.sort(intervals, new myComparator());
    int dp[] = new int[intervals.length];
    dp[0] = 1;
    int ans = 1;
    for (int i = 1; i < dp.length; i++) {
      int max = 0;
      for (int j = i - 1; j >= 0; j--) {
        if (!isOverlapping(intervals[j], intervals[i])) {
          max = Math.max(dp[j], max);
        }
      }
      dp[i] = max + 1;
      ans = Math.max(ans, dp[i]);
    }
    return intervals.length - ans;
  }
}

Complexity:

time: O(N logN) space: O(1)

[ysy0707]

思路：贪心，重写排序方法，模拟（字节面试做过）

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        //先排序,也可以重写comparator方法
        //Arrays.sort(intervals,new Comparator<int[]>(){
        //    @Override
        //    public int compare(int[] o1, int[] o2){
        //        return o1[0] - o2[0];
        //    }
        //});
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        //记录区间尾部的位置
        int end = intervals[0][1];
        //需要移除的数量
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                //如果重叠了，必须要移除一个，所以count要加1，
                //然后更新尾部的位置，我们取尾部比较小的
                end = Math.min(end, intervals[i][1]);
                count++;
            } else {
                //如果没有重叠，就不需要移除，只需要更新尾部的位置即可
                end = intervals[i][1];
            }
        }
        return count;
    }
}

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

[zhuzuojun]

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 按照右边界从小到大排序
        Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
        int res = 0;
        int lastEnd = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            if (interval[0] >= lastEnd) lastEnd = interval[1];
            else res++;
        }

        return res;
    }
}

[chenming-cao]

解题思路

贪心。为了使移除区间数最小，我们要尽可能多的保留不重复的区间。

做法：先将intervals排序，按end从小到大排，相同end按start从小到大排。注意不能先按start排，有可能出现start小但end特别大的区间，造成错误结果。然后找重复区间个数：用双指针遍历排好序的intervals，双指针起始l = 0, r = 1，增加r，找到跟下标为l的interval不重叠的第一个区间，重叠区间判断条件intervals[l][1] > intervals[r][0]，用res记录此过程中出现的重复区间数。找到不重复区间后更新l = r, r = r + 1继续遍历，直到r越界为止。最后返回res即为结果。

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int len = intervals.length;
        if (len < 2) return 0;
        // sort the intervals based on end then start, 
        // this ensures that we can keep as many intervals as possible, like meeting scheduling problem
        Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);
        int res = 0;
        int l = 0, r = 1;
        while (r < len) {
            // overlap occurs when the second interval's end is smaller than the first interval's end
            while (r < len && intervals[l][1] > intervals[r][0]) {
                res++;
                r++;
            }
            if (r == len) break;
            // check the next pair
            l = r;
            r++;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，n为intervals数组长度，因为需要排序
• 空间复杂度：O(1)

[JiangyanLiNEU]

Greedy

• sort the array by item[0], if item[0] is equal, then sort by item[1]
• if array[i] and array[i+1] overlap, then remove the one with greater item[1]
• runtime = O(nlogn) space = O(1)

  JavaScript

  var eraseOverlapIntervals = function(intervals) {
  intervals.sort(function(item1, item2){
      return item1[0]-item2[0] || item1[1]-item2[1];
  });
  let res = 0;
  let left = 0;
  let right = 1;
  while (right<intervals.length){
      [a1,b1] = intervals[left]; 
      [a2,b2] = intervals[right];
      if (a2 >=b1){
          left = right;
          right++;
      }else{
          res++;
          if (b2 < b1){
              left = right;
              right++;
          }else{
              right++;
          };
      };
  };
  return res;
  };

  Python

  class Solution(object):
  def eraseOverlapIntervals(self, intervals):
      intervals.sort()
      left = 0
      right = 1
      res = 0
      while right<len(intervals):
          [a1,b1] = intervals[left]
          [a2,b2] = intervals[right]
          if a2 >= b1:
              left = right
              right += 1
          else:
              res += 1
              if b2 > b1:
                  right += 1
              else:
                  left = right
                  right += 1
      return res

[ZacheryCao]

Idea:

Greedy. Sort the intervals by its start time. Scan from right to left to get how many intervals (amount) we need to remove to maintain there are not overlaps. The reason we scan from right to left is beacsue it may have intervals with large range with the earliest start time that overlaps all other intervals. If we scan the array from left to right, it can result in removing all other intervals. If we scan from right to left, it can ensure that we handle the intervals with lastest start time first, which can avoid this issue.

Code:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key = lambda x:x[0])
        start, end, ans = intervals[-1][0], intervals[-1][1], 0
        for i in range(len(intervals)-2, -1, -1):
            if intervals[i][1] > start:
                ans += 1
                continue
            start, end = intervals[i][0], intervals[i][1]
        start, end = intervals[0][0], intervals[0][1]
        return ans

Complxity:

TIme: O(N log N). The domain complexity is the sort with O(N log N). Scanning only needs O(N) Space: O(1)

[laofuWF]

# sort by end time
# find max number of intervals that will not have overlap
# note: use curr_right track the latest end time that will not cause overlapping
# res = total - max_intervals

# time: O(N/logN)
# space: O(1)

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key = lambda x:x[1] )
        valid_count = 1
        curr_right = intervals[0][1]
        for i, interval in enumerate(intervals[1:]):
            if interval[0] >= curr_right:
                valid_count += 1
                curr_right = interval[1]

        return len(intervals) - valid_count

[heyqz]

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

        res = 0
        preEnd = intervals[0][1]

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

        return res

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

[ginnydyy]

Problem

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

Notes

• Greedy
• To form the longest non-decreasing intervals, we need to start from the interval with the smallest right edge.
• And the next best interval is an interval with the smallest right edge, and its left edge is greater than or equal to the previous selected interval.
• So on and so forth, until iteraing all the interval candidates, we form the longest non-decreasing intervals.
• Then the result is the number of interval candidates minus the number of the selected intervals in the longest non-decreasing intervals.

Solution

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

        Comparator<int[]> comparator = new Comparator<>(){
            public int compare(int[] a, int[] b){
                return a[1] - b[1];
            }
        };

        Arrays.sort(intervals, comparator);
        System.out.println("sorted: " + Arrays.deepToString(intervals));

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

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

        return intervals.length - count;
    }
}

Complexity

• Time: O(nlongn), n is the length of the given intervals array. O(nlong) for sorting. O(n) for iterating the intervals. Overall is O(nlongn).
• Space: It depends on the sorting. There is no extra space required by the sorting.

[yachtcoder]

O(nlgn), O(1) Greedy or as a LIS variation.

class Solution:
    def eraseOverlapIntervals(self, ins: List[List[int]]) -> int:
        ins.sort(key = lambda x: x[1])
        # greedy
        cnt = 1
        pe = ins[0][1]
        for i in range(1, len(ins)):
            s, e = ins[i]
            if pe <= s:
                cnt += 1
                pe = e
        return len(ins) - cnt
        # LIS
        lis = []
        for s, e in ins:
            idx = bisect_right(lis, s)
            if idx == len(lis):
                lis.append(e)
        return len(ins) - len(lis)

[littlemoon-zh]

If we sort by the start, then:

[1, 100], [2,3], [3,4], [4,5], [10,20], [20, 24]

In this case, it's obviously wrong! Sort by the end so that current interval has no impact on intervals behind.

var eraseOverlapIntervals = function(intervals) {
    intervals.sort((x, y) => {
        if (x[1] !== y[1]) return x[1] - y[1];
        return x[0] - y[0];
    })
    let res = 0;
    let [l, r] = intervals[0];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < r) {
            res += 1;
        } else {
            [l, r] = intervals[i];
        }
    }
    return res;
};

Time: O(nlogn) sort Space: O(1)

[xj-yan]

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

Time Complexity: O(nlogn), Space Complexity: O(1)

[zhy3213]

思路

贪心 可太难了

代码

    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals=sorted(intervals,key=lambda x: x[1])
        r=intervals[0][1]
        res=1
        for i in range(1,len(intervals)):
            if intervals[i][0]>=r:
                r=intervals[i][1]
                res+=1
        return len(intervals)-res

[CoreJa]

思路

不得不说贪心算法要比动规难想很多。这个题其实用动规能是修仙O(n^2)的复杂度，和最长子序列长度类似。

关于这个题，关键在两点：

• 按照右界排序
• 取不overlap的元素

然后用个计数器就能得到最大count，再来length减掉即可。

算法写起来非常容易，因为逻辑很简单。关键是很难想到/证明为什么这样就能取到最大的区间。

其实可以这么想：按照右界排序可保证从左边开始取的右边界最小，即剩下的空间就最大，那这种取法就能得到最多区间

代码

    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # 贪心法YYDS
        intervals.sort(key=lambda t: t[1])
        left, right = intervals[0]
        count = 1
        for i in range(1, len(intervals)):
            if right <= intervals[i][0]:
                count += 1
                left, right = intervals[i]
        return len(intervals) - count

[siyuelee]

参考答案 - 动态规划

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        n = len(intervals)
        if n == 0: return 0
        dp = [1] * n
        res = 1
        intervals.sort(key=lambda x: x[0])

        for i in range(n):
            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)

[pophy]

思路

• 转化思路为： 求最多能保留多少interval 记为n 则原题答案最少为intervals.length - n
• 贪心思路 - 当前interval记为 cur， 前一个Interval在end处结束
  • 如果cur[0] >=end 则当前cur可以放入 end = cur[1]
  • 如果cur[0] < end 则直接跳过该cur

Java Code

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
        int end = Integer.MIN_VALUE, count = 0;
        for (int[] cur : intervals) {
            if (cur[0] >= end) {
                count++;
                end = cur[1];
            }
        }
        return intervals.length - count;
    }

时间&空间

• 时间 O(n)
• 空间 O(1)

[zol013]

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]
        count = 1
        n = len(intervals)

        for i in range(n):
            if right <= intervals[i][0]:
                count += 1
                right = intervals[i][1]
        return n - count

[biancaone]

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

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

        count = 0
        prev_end = -sys.maxsize

        for interval in intervals:
            if interval[0] >= prev_end:
                prev_end = interval[1]
            else:
                count += 1

        return count

[Daniel-Zheng]

思路

贪心。

代码(C++)

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {return u[1] < v[1];});
        int count = 1, 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)

[ghost]

题目

435. Non-overlapping Intervals

思路

Greedy and sort

代码

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals)<=1: return 0

        intervals.sort(key = lambda x:x[0])
        res = i = 0

        for j in range(1, len(intervals)):
            if intervals[j][0] < intervals[i][1]:
                res += 1
                if intervals[j][1] >= intervals[i][1]: continue

            i = j

        return res

复杂度

Space: O(1) Time: O(nlogn)

[chen445]

代码

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

复杂度

Time: O(nlogn)

Space: O(1)

[zjsuper]

Change to LIS problem, dp Time O(N^2)

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if n == 0: return 0
        # dp[i] from 0 to i, what's the max number of increasing elements, include i
        dp = [1] * n
        ans = 1
        intervals.sort(key=lambda a: a[0])
        for i in range(n):
            for j in range(i):
                if intervals[j][1] <= intervals[i][0]:
                    dp[i] = max(dp[j]+1, dp[i])

        return n- max(dp)

[yan0327]

思路： 先对结束时间排序，对集合进行遍历，令最左边作为基础，for i := range =》找到第一个起始时间大于等于参考区间的， 然后max++，同时把参考区间移动到当前区间，继续比较 =》求需要移除区间的最小数量 = 区间中的最长满足条件子列

func eraseOverlapIntervals(intervals [][]int) int {
    n := len(intervals)
    sort.Slice(intervals,func(i,j int)bool{
        x := intervals
        return  x[i][1]<x[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
}

时间复杂度：O（nlogn） 空间复杂度：O（1）

[zhangzz2015]

思路

• 对区间的end time 进行从小到大排序，从后往前遍历，当两个区间没有重叠，我们不删除，如果两个区间有重叠，我们选择那一个？我们选择start time 更大的，这样后面的区间有更大的概率不和当前选择的区间重叠。
• 方法1，采用栈的方法，栈中存放所有没有重叠的区间。当当前的区间和栈顶的区间有重合，我们比较start time，如果栈顶start time 更大，则keep栈，删除当前的区间，如果当前的start time 更大，则删除栈顶的区间，把当前的区间放入栈顶，最后返回 interval size - stack size，时间复杂度为O(nlogn) + o(n)，空间复杂度为O(n)
• 方法2，因为题目只需要计算删除数，可优化内存，只记录栈顶区间的index即可，时间复杂度为O(nlogn)+o(n)，空间复杂度为O(1)。

关键点

代码

• 语言支持：c

c Code:

struct cmp
{
   bool operator()(vector<int>& node1, vector<int>& node2)
   {
       if(node1[1] == node2[1])
           return node1[0] < node2[0]; 
       return node1[1] < node2[1]; 
   }
}; 
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {

        sort(intervals.begin(), intervals.end(), cmp()); 
        vector<vector<int>> stack; 
        for(int i = intervals.size()-1; i>=0; i--)
        {
            if(stack.size()==0)
            {
                stack.push_back(intervals[i]); 
            }
            else if( stack.back()[0]>=intervals[i][1]) // nonoverlap
            {
                stack.push_back(intervals[i]); 
            }
            else if(stack.back()[0]<intervals[i][0])
            {
                stack.pop_back();
                stack.push_back(intervals[i]); 
            }
        }

        return intervals.size() - stack.size(); 

    }
};

struct cmp
{
   bool operator()(vector<int>& node1, vector<int>& node2)
   {
       if(node1[1] == node2[1])
           return node1[0] < node2[0]; 
       return node1[1] < node2[1]; 
   }
}; 
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {

        sort(intervals.begin(), intervals.end(), cmp()); 
        int topNode = intervals.size()-1; 
        int ret =0; 
        for(int i = intervals.size()-2; i>=0; i--)
        {
            if( intervals[topNode][0]>=intervals[i][1]) // nonoverlap
            {
                topNode=i; 
            }
            else if(intervals[topNode][0]<intervals[i][0])
            {
                ret++; 
                topNode = i; 
            }
            else
            {
                ret++; // topNode don't change. 
            }
        }

        return ret; 

    }
};

[itsjacob]

Intuition

• [tags] two-pointers, greedy
• for two neighoring intevals vi & vj, there're four cases
  • vi contains vj, remove the longer one (vi)
  • vj contains vi, remove the longer one (vj)
  • vi partially overlaps with vj, remove vj because vj might overlap with vj+1
  • vi doesn't overlap with vj, move on

Implementation

class Solution
{
public:
  int eraseOverlapIntervals(vector<vector<int>> &intervals)
  {
    if (intervals.size() <= 1) return 0;
    std::sort(intervals.begin(), intervals.end(),
              [](vector<int> &i1, vector<int> &i2) { return i1[0] < i2[0] || (i1[0] == i2[0] && i1[1] < i2[1]); });
    // for vi and vj in intervals
    // case 1:
    //   contains:
    //     - vi contains vj, remove vi, i = j, j++
    //     - vj contains vi, remove vj, j++
    // case 2:
    //    overlap: remove latter (vj), j++, we remove latter because vj might overlap with vj+1
    // case 3:
    //    non-overlap: i = j, j++
    int i{ 0 };
    int j{ 1 };
    int count{ 0 };
    while (j < intervals.size()) {
      auto &vi = intervals[i];
      auto &vj = intervals[j];
      if (vi[0] <= vj[0] && vi[1] >= vj[1]) {
        // case 1.1: vi contains vj
        i = j;
        j++;
        count++;
      } else if (vi[0] >= vj[0] && vi[1] <= vj[1]) {
        // case 1.2: vj contains vi
        j++;
        count++;
      } else if (vi[1] > vj[0]) {
        // case 2: vi partially overlaps with vj
        // always remove vj because there's a possibility vj will overlap with vj+1
        j++;
        count++;
      } else {
        // case 3: vi has no overlap with vj
        i = j;
        j++;
      }
    }
    return count;
  }
};

Complexity

• Time complexity: O(NlogN) for the sorting
• Space complexity: O(1)

[wangyifan2018]

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)
        ans = 1
        right = intervals[0][1]

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

        return n - ans

[joeytor]

思路

先按照 区间结尾 升序排序

思路是 每一次选 结尾最靠前的区间, 因为这样的选择后面可能可以选更多的区间, 因为区间的结尾会更早, 这样对后面区间开始的要求可以变得更小 (后面区间的开始可以更靠前)

遍历所有的排序后的区间, 如果这个区间的开头 s

如果 s < cur_end, 代表这个区间跟 上一个被选择的区间有 overlap, 那么根据上面的贪心的思想, 不选择这个区间, num += 1 因为要 remove 这个区间

如果 s ≥ cur_end, 代表这个区间跟上一个被选择的区间没有 overlap, 那么根据贪心的思想, 因为是按照结尾排序后的数组, 代表后面的 interval 结尾更靠后, 所以选择现在这个区间

最后返回 num 就是被 remove 的区间的个数

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

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

        cur_end = -float('inf')
        num = 0
        for s, e in intervals:
            if s < cur_end :
                num += 1
            else:
                cur_end = e

        return num

复杂度

时间复杂度: O(nlogn) 排序的复杂度是 O(nlogn), 遍历的时间复杂度是 O(n)

空间复杂度: O(logn) 排序的空间复杂度

[jocelinLX]

为什么在某些情况下，从左往右比不是删除最小区间： class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort() if len(intervals) <=0: return 0 res=0 n=len(intervals)-1 x = intervals[n][0] i=n-1 while i >= 0: if intervals[i][1] <= x: x=intervals[i][0] i-=1 else: i-=1 res+=1 return res

[Francis-xsc]

思路

贪心 会场安排问题 结果=总数-安排会场数

代码

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int len=intervals.size();
        if(len==0)
            return 0;
        int res=1;
        sort(intervals.begin(),intervals.end(),[](const auto& u, const auto& v) {
            return u[1] < v[1];
        });
        int right=intervals[0][1];
        for(int i=1;i<len;i++){
            if(intervals[i][0]>=right){
                res++;
                right=intervals[i][1];
            }
        }
        return len-res;
    }
};

复杂度分析

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

[jocelinLX]

为什么从左往右比较的时候再某些情况下不是最小删除区间，但是从右往左比就不会出现这个问题？

class Solution:

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

​        intervals.sort()

​        if len(intervals) <=0:

​            return 0

​        res=0

​        n=len(intervals)-1

​        x = intervals[n][0]

​        i=n-1

​        while i >= 0:

​            if intervals[i][1] <= x:

​                x=intervals[i][0]

​                i-=1

​            else:

​                i-=1

​                res+=1

​        return res

[wangzehan123]

代码

• 语言支持：Java

Java Code:

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 按结尾进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

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

        return ans;
    }
}

[st2yang]

思路

• 贪心：保留结束时间早的

代码

• python

  class Solution:
  def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
      end = float('-inf')
      res = 0
  
      for s, e in sorted(intervals, key=lambda x: x[1]):
          if s >= end:
              end = e
          else:
              res += 1

复杂度

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

[ABOUTY]

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        """
        以[[1,2],[2,3],[3,4],[1,3]]为例
        先按开始时间排序，[[1,2],[1,3],[2,3],[3,4]]
        再将每个区间的开始时间和前一区间的结束时间作比较， 如果start[i]>end[i-1], 则最长上升子序列长度x+=1， 最终答案为 n-x
        """
        n = len(intervals)
        dp = [1] * n
        intervals.sort(key=lambda x: x[0])
        ans = 1

        for i in range(1, n):
            for j in range(i - 1, -1, -1):
                # 在intervals[i]左边找递增区间，找到一个就更新答案并跳出
                if intervals[j][1] <= intervals[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    ans = max(ans, dp[i])
                    break
        return n - ans

[AruSeito]

var eraseOverlapIntervals = function (intervals) {
    let res = 1;

    intervals.sort((a,b)=>a[0]-b[0]);
    let start = intervals[intervals.length-1][0];
    for(let i = intervals.length - 1 ; i >=0;i--){
        if(intervals[i][1]<=start){
            start = intervals[i][0];
            res++;
        }
    }

    return intervals.length - res;
};

[kidexp]

thoughts

看的题解，按照interval的end time 升序排列，每次找剩下interval里面跟已有的non overlap的interval 没有overlap的最小右端

code

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

complexity

Time O(nlgn) Space O(1)

[ai2095]

435. Non-overlapping Intervals

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

Topics

• Greedy

思路

Greedy

代码 Python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 0:
            return 0
        intervals.sort()
        prev = intervals[0]
        cnt = 1
        for i in range(len(intervals)):
            prev_start, prev_end = prev
            cur_start, cur_end = intervals[i]
            if prev_end <= cur_start:
                prev = intervals[i]
                cnt += 1
            elif prev_end >= cur_end:
                prev = intervals[i]

        return len(intervals) - cnt

复杂度分析

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

[kennyxcao]

435. Non-overlapping Intervals

Intuition

• Greedy

Code

/**
 * @param {number[][]} intervals
 * @return {number}
 */
const eraseOverlapIntervals = function(intervals) {
  const n = intervals.length;
  if (n === 0) return 0;
  intervals.sort((a, b) => a[0] - b[0]); // sort by start ascending
  let delCount = 0;
  let prevEnd = intervals[0][1];
  for (let i = 1; i < n; i++) {
    const [currStart, currEnd] = intervals[i];
    if (currStart < prevEnd) { // overlapped with prev
      prevEnd = Math.min(prevEnd, currEnd); // use the smaller end
      delCount += 1;
    } else { // no overlap with prev, use currEnd as the new end
      prevEnd = currEnd;
    }
  }
  return delCount;
};

Complexity Analysis

• Time: O(nlogn)
• Space: O(1)

[zhiyuanpeng]

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        intervals.sort()
        left = 0
        right = 1
        res = 0
        while right<len(intervals):
            [a1,b1] = intervals[left]
            [a2,b2] = intervals[right]
            if a2 >= b1:
                left = right
                right += 1
            else:
                res += 1
                if b2 > b1:
                    right += 1
                else:
                    left = right
                    right += 1
        return res

[Yufanzh]

Intuition

This is an interval schedule problem\ approach: first sort the interval by the end (ascend)\ Then take the interval with the earliest ending one, delete the ones that overlap with this interval.

Algorithm in python3

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        #sort by interval end
        intervals.sort(key=lambda a:a[1])

        count = 1
        end = intervals[0][1]
        for interval in intervals:
            start = interval[0]
            if start >= end:
                count += 1
                end = interval[1]
        return len(intervals) - count

Complexity Analysis

• Time complexity: O(nlogn) due to sort
• Space complexity: O(n)

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

[shixinlovey1314]

Title:435. Non-overlapping Intervals

Question Reference LeetCode

Solution

In order to find out the minimum number of intervals to remove, we could instead find the maximum interval that we could keep. To do so, we first sort the original intervals, then for each one, compare with the previous one see if it can be kept.

Code

bool compare(const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
}

class Solution {
public:

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), compare);
        int keep = 1;
        int r = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= r) {
                keep++;
                r = intervals[i][1];
            }
        }

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

Complexity

Time Complexity and Explanation

O(nlogn), need to sort the intervals

Space Complexity and Explanation

O(1)

[chun1hao]

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

[Mrhero-web]

class Solution(object): def eraseOverlapIntervals(self, intervals): intervals.sort() left = 0 right = 1 res = 0 while right<len(intervals): [a1,b1] = intervals[left] [a2,b2] = intervals[right] if a2 >= b1: left = right right += 1 else: res += 1 if b2 > b1: right += 1 else: left = right right += 1 return res

[learning-go123]

思路

关键点

• 贪心

代码

• 语言支持：Go

Go Code:

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    res := 0
    end := intervals[0][1]
    for i:=1;i<len(intervals);i++ {
        if intervals[i][0] >= end {
            end = intervals[i][1]
        } else {
            res++
        }
    }
    return res
}

复杂度分析

令 n 为数组长度。

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

[freesan44]

思路

采用dp方式，把符合递增子序列的放入dplist中

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        length = len(intervals)
        intervals.sort(key= lambda x:x[0])
        dp = [1] * length
        for i in range(length):
            for j in range(i-1,-1,-1):
                # print(intervals[i],intervals[j],dp)
                startTime = intervals[i][0]
                endTime = intervals[j][1]
                #如果符合递增，就放入dp中，形成完美递增序列
                if startTime >= endTime:
                    dp[i] = max(dp[i],dp[j]+1)
                    break
        # print(dp)
        return length - max(dp)

if __name__ == '__main__':
    nums = [ [1,2], [2,3], [3,4], [1,3] ]
    nums = [[1, 2], [1, 2], [1, 2]]
    nums = [[1, 2], [2, 3]]
    nums = [[1, 2], [2, 3], [3, 4], [1, 3]]
    nums = [[1,100],[11,22],[1,11],[2,12]]
    res = Solution().eraseOverlapIntervals(nums)
    print(res)

复杂度分析

令 n 为数组长度。

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

[tongxw]

思路

按右边界排序，选右边界最小的区间当第一个区间； 然后每次都选择右边界最小的，且不和上一个区间重叠的区间，这样尽量给右面留足够多的空间，最后得到最优解。

代码

  public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (t1, t2) -> t1[1] - t2[1]);
    int n = intervals.length;
    int ans = 1;
    int right = intervals[0][1];
    for (int i=1; i<n; i++) {
      if (intervals[i][0] >= right) {
        ans++;
        right = intervals[i][1];
      }
    }

    return n - ans;
  }

TC: O(NLogN) 排序 SC: O(LogN) 排序

[machuangmr]

题目435. 无重叠区间

思路

• 先按照右边界排序，然后计算非交叉的区间
• 参考官方题解

  代码

  class Solution {
  public int eraseOverlapIntervals(int[][] intervals) {
      if(intervals.length < 2) return 0;
        // 先排序，先按照区间的右边界进行排序
      Arrays.sort(intervals, new Comparator<int[]>() {
          @Override
          public int compare(int[] o1, int[] o2) {
              if (o1[1] != o2[1]) {
                  return Integer.compare(o1[1], o2[1]);
              } else {
                  return Integer.compare(o1[0], o2[0]);
              }
          }
      });
      int count = 1;
      int endge = intervals[0][1];
      for(int i = 1; i < intervals.length;i++) {
          if (endge <= intervals[i][0]) {
              count ++;
              endge = intervals[i][1];
          }
      }
      return intervals.length - count;
  }   
  }

  复杂度

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

[thinkfurther]

思路

最长递增子序列

代码

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals = sorted(intervals, key = lambda x: x[0])

        n = len(intervals)        
        dp = [1] * n

        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)

代码

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

空间复杂度：O(N)

[mixtureve]

class Solution {
  class myComparator implements Comparator<int[]> {
    public int compare(int[] a, int[] b) {
      return a[1] - b[1];
    }
  }
  public boolean isOverlapping(int[] i, int[] j) {
    return i[1] > j[0];
  }
  public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
      return 0;
    }
    Arrays.sort(intervals, new myComparator());
    int dp[] = new int[intervals.length];
    dp[0] = 1;
    int ans = 1;
    for (int i = 1; i < dp.length; i++) {
      int max = 0;
      for (int j = i - 1; j >= 0; j--) {
        if (!isOverlapping(intervals[j], intervals[i])) {
          max = Math.max(dp[j], max);
        }
      }
      dp[i] = max + 1;
      ans = Math.max(ans, dp[i]);
    }
    return intervals.length - ans;
  }
}