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

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

[Abby-xu]

思路

Sorting + iteration compare

代码

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

复杂度

O(nlogn)

[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

[Ryanbaiyansong]

class Solution:
    def eraseOverlapIntervals(self, a: List[List[int]]) -> int:
        A = sorted(a, key = lambda it: it[1])
        # # 按照终点排序
        # i = j = 0
        # ans = 0
        # n = len(a)
        # while i < n:
        #     if j < n and A[j][0] < A[i][1]:
        #         while j < n and A[j][0] < A[i][1]:
        #             j += 1
        #         ans += 1
        #         i = j
        #     else:
        #         i += 1

        # return n - ans
        n = len(a)
        count = 1
        x_end = A[0][1]
        for start, end in A:
            if start >= x_end:
                x_end = end 
                count += 1

        return n - count

[buer1121]

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]) count=1 #记录非交叉区间的个数 end=intervals[0][1] #记录区间分割点 for i in range(1,n): if end<=intervals[i][0]: count+=1 end=intervals[i][1] return n-count

[luhaoling]

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

[snmyj]

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n=intervals.size();
        vector<int> dp(n,1);
        sort(intervals.begin(),intervals.end());   // sort
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(intervals[j][1]<=intervals[i][0]){   // search the first point
                   dp[i]=dp[j]+1;                            // renew
                   break;
                }

            }

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

    }
};

[Elsa-zhang]

# 435. 无重叠区间
''' 贪心
    区间划分问题 
'''
class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]):
        n = len(intervals)
        intervals = sorted(intervals, key=lambda a: a[1])
        ans = 1
        right = intervals[0][1]

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

intervals = [[1,2],[2,3],[3,4],[1,3]]
solution = Solution()
ans = solution.eraseOverlapIntervals(intervals)
print(ans)

[whoam-challenge]

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

    intervals.sort()
    n = len(intervals)
    f = [1]

    for i in range(1, n):
        f.append(max((f[j] for j in range(i) if intervals[j][1] <= intervals[i][0]), default=0) + 1)

    return n - max(f)

[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)

[zywang0]

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

[tiandao043]

思路

贪心

代码

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(nlog⁡n) O(logn)

[klspta]

class Solution {
    public int eraseOverlapIntervals(int[][] q) {
        Arrays.sort(q, (a, b) -> a[1] - b[1]);
        int res = 1;
        int r = q[0][1];
        for(int i = 1; i < q.length; i++){
            if(q[i][0] >= r){
                res++;
                r = q[i][1];
            }
        }

        return q.length - res;
    }
}

[A-pricity]

/**
 * @param {number[][]} intervals
 * @return {number}
 */
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
};

[paopaohua]

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

[RestlessBreeze]

code

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

[bookyue]

code

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[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]) {
                j++;
                res++;
            }

            i = j;
        }

        return res;
    }

[saitoChen]

思路

贪心算法

代码

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

  return intervals.length - count
}

[mayloveless]

思路

贪心

代码

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 res = 1;
    for (let i = 1; i < n; ++i) {
        if (intervals[i][0] >= right) { // 不重叠
            ++res;//则选中它
            right = intervals[i][1];
        }
    }
    return n - res;
};

复杂度

时间 O（n logn）排序 空间 O（n logn）排序

[Jetery]

class Solution {
public:
    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;
    }

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

};

[Elon-Lau]

class Solution { public: int eraseOverlapIntervals(vector<vector>& 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; }

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

};