LeetCode75| 区间集合

本文主要是介绍LeetCode75| 区间集合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

435 无重叠区间

452 用最少的箭引爆气球

---

435 无重叠区间

class Solution {
public:static bool cmp(vector<int>&a,vector<int>&b){return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {int res = 0;sort(intervals.begin(),intervals.end(),cmp);for(int i = 1;i < intervals.size();i++){if(intervals[i][0] >= intervals[i - 1][1]){intervals[i][1] = max(intervals[i][1],intervals[i - 1][1]);}else{intervals[i][1] = min(intervals[i][1],intervals[i - 1][1]);res++;}}return res;}
};

时间复杂度O(nlogn)

空间复杂度O(logn)//排序所需要的栈空间

452 用最少的箭引爆气球

class Solution {
public:static bool cmp(vector<int>& a,vector<int>& b){return a[0] < b[0];}int findMinArrowShots(vector<vector<int>>& points) {int res = 1;sort(points.begin(),points.end(),cmp);    for(int i = 1;i < points.size();i++){if(points[i][0] <= points[i - 1][1]){points[i][1] = min(points[i][1],points[i - 1][1]);points[i][0] = max(points[i][0],points[i - 1][0]);}else res++; }return res;}
};

时间复杂度O(nlogn)

空间复杂度O(logn)//排序所需要的栈空间

这篇关于LeetCode75| 区间集合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---