无重叠区间 中等🌟🌟🌟🌟

课后作业

问题描述

原文链接：435. 无重叠区间

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

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

代码实现

Java

class Solution {
    /*
        转化问题：保存最大的区间数量，使得区间不重叠，比如最大数间数量为max，
        return 数组长度 - max。
        intervals = [,[3,4], ];
        怎么选择：我们要选择右边界比较小的区间
        [1,2],[2,3]，[3,4]

        步骤：
        对数组排序，要以第二个元素来排序
        之后遍历数组，如果遇到不重叠的就选下来

    */
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length <= 1) return 0;

        //排序
        Arrays.sort(intervals, new Comparator<int[]>(){
            //重写compare
            public int compare(int[] s1, int[] s2){
                return s1[1] - s2[1];
            }
        });

        //
        int max = 1;
        int right = intervals[0][1];

        for(int i = 1; i < intervals.length; i++){

            if(intervals[i][0] >= right){
                max++;
                right = intervals[i][1];
            }
        }
        return intervals.length - max;
    }
}

Python

class Solution:
    def eraseOverlapIntervals(self, intervals):
        if len(intervals) <= 1:
            return 0

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

        max_count = 1
        right = intervals[0][1]

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

        return len(intervals) - max_count

C++

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

        // 排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

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

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

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

Go

import "sort"

func eraseOverlapIntervals(intervals [][]int) int {
    if len(intervals) <= 1 {
        return 0
    }

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

    maxCount := 1
    right := intervals[0][1]

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= right {
            maxCount++
            right = intervals[i][1]
        }
    }

    return len(intervals) - maxCount
}

shuaidi永久会员

收藏 海报 链接