【算法与数据结构】435、LeetCode无重叠区间

2023-12-29 11:54:07

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解

一、题目

在这里插入图片描述

二、解法

??思路分析:思路和【算法与数据结构】452、LeetCode用最少数量的箭引爆气球类似,也是排序+找重叠区间。因为题目要求去掉重叠区间,所以要找挨着的重叠区间数量。因此在if语句中稍作修改。
??程序如下

class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {
	if (a[0] == b[0]) return a[1] < b[1];
	return a[0] < b[0];
}
public:
	int eraseOverlapIntervals(vector<vector<int>>& intervals) {
		int result = 0;
		sort(intervals.begin(), intervals.end(), cmp);
		for (int i = 1; i < intervals.size(); i++) {
			if (intervals[i][0] < intervals[i - 1][1]){ // 如果第i个区间和第i-1个区间挨着,移除区间数+1
				result++;
				intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠区间最小右边界
			}
		}
		return result;
	}
};

复杂度分析:

  • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),一个快速排序。
  • 空间复杂度: O ( 1 ) O(1) O(1),有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要O(n)的栈空间
    可以看出代码并不复杂。

三、完整代码

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {
	if (a[0] == b[0]) return a[1] < b[1];
	return a[0] < b[0];
}
public:
	int eraseOverlapIntervals(vector<vector<int>>& intervals) {
		int result = 0;
		sort(intervals.begin(), intervals.end(), cmp);
		for (int i = 1; i < intervals.size(); i++) {
			if (intervals[i][0] < intervals[i - 1][1]){ // 如果第i个区间和第i-1个区间挨着,移除区间数+1
				result++;
				intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠区间最小右边界
			}
		}
		return result;
	}
};

int main() {
	vector<vector<int>> intervals = { {1, 2}, {2, 3},{3, 4},{1, 3} };
	Solution s1;
	int result = s1.eraseOverlapIntervals(intervals);
	cout << "结果:" << result << endl;
	system("pause");
	return 0;
}

end

文章来源:https://blog.csdn.net/qq_45765437/article/details/135286529
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。