题目链接

435. 无重叠区间 - 力扣（LeetCode）

题目描述

给定区间集合 intervals，其中intervals[i] = [starti, endi]。

移除区间，使得剩余区间互不重叠。

输出需要移除区间的最少数量。

[1, 2] 和 [2, 3]是不重叠的

输入输出样例

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

题目解释

区间的结尾很重要，如果我们保留的不重叠的区间的结尾越小，留给其他区间的空间就越大。

代码

个人实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if (intervals.empty() || n == 1) {
            return 0;
        }
        sort(intervals.begin(), intervals.end(),
             [](vector<int> a, vector<int> b) { return a[1] < b[1]; });

        int total = 0, prev = intervals[0][1];
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] < prev) {
                ++total;
            } else {
                prev = intervals[i][1];
            }
        }
        return total;
    }
};

官方实现

作者：力扣官方题解
链接：435. 无重叠区间 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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