淄博网站设计策划方案公司,苏州网站建设多少钱,如何制作小程序二维码,合肥网站建设与设计文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;思路和【算法与数据结构】452、LeetCode用最少数量的箭引爆气球类似#xff0c;也是排序找重叠区间。… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析思路和【算法与数据结构】452、LeetCode用最少数量的箭引爆气球类似也是排序找重叠区间。因为题目要求去掉重叠区间所以要找挨着的重叠区间数量。因此在if语句中稍作修改。 程序如下
class Solution {
static bool cmp(const vectorint a, const vectorint b) {if (a[0] b[0]) return a[1] b[1];return a[0] b[0];
}
public:int eraseOverlapIntervals(vectorvectorint 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个区间挨着移除区间数1result;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 vectorint a, const vectorint b) {if (a[0] b[0]) return a[1] b[1];return a[0] b[0];
}
public:int eraseOverlapIntervals(vectorvectorint 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个区间挨着移除区间数1result;intervals[i][1] min(intervals[i - 1][1], intervals[i][1]); // 更新重叠区间最小右边界}}return result;}
};int main() {vectorvectorint intervals { {1, 2}, {2, 3},{3, 4},{1, 3} };Solution s1;int result s1.eraseOverlapIntervals(intervals);cout 结果 result endl;system(pause);return 0;
}end
