当前位置：首页 > ops >正文

无重叠区间问题

ops 2025/7/14 15:57:32

题目描述：
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。
注意只在一点上接触的区间是不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
leetcode链接：https://leetcode.cn/problems/non-overlapping-intervals/description/

开始思路

可以注意到，重叠区间可通过判断区间左右端点是否相交进行判断。因此首先要对给出的区间进行排序，然后依次计算后续区间是否重叠，并更新区间端点。但是该方法没有考虑到图一所示情况，因此，只能通过部分测试案例（提交结果见图二）

图一，此时应选择2、3而不是1

图二，仅通过部分测试用例

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());int overLap = 0;int L, R;L = intervals[0][0];R = intervals[0][1];for(int i=0; i<intervals.size(); i++){cout<<intervals[i][0]<<intervals[i][1]<<' ';}for (int _i = 1; _i < intervals.size(); _i++) {if (intervals[_i][0] < R) {overLap++;} else {R = intervals[_i][1];}}return overLap;}
};

贪婪算法

开始算法的问题在于，题目要求尽可能多的容纳区间，即队列的排序条件应为：1、最先结束；2、最早开始，且以上两个条件中，条件一的优先级＞条件二。是故，应为以下代码：

bool compare(const vector<int>& k, const vector<int>& l) {if (k[1] != l[1])return k[1] < l[1];return k[0] < l[0];
}
class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), compare);int overLap = 0;int end = 0;for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] >= intervals[end][1]) {end = i;} else {overLap++;}}return overLap;}
};