响应式网站方案,wordpress管理员插件,百雀羚网站建设模版,寿光专业做网站的公司有哪些“任世界多宽广#xff0c;停泊在这港口~” 区间问题#xff0c;涉及到最多的就是 取交集 和 并集的概念。我们使用C排序算法后#xff0c;其默认规则就是按照 “左排序”进行的。因而#xff0c;我们实质上注意的是每一个区间的 右端点#xff0c;根据题目要求#xff…
“任世界多宽广停泊在这港口~” 区间问题涉及到最多的就是 取交集 和 并集的概念。我们使用C排序算法后其默认规则就是按照 “左排序”进行的。因而我们实质上注意的是每一个区间的 右端点根据题目要求总结规律指定出策略解决问题。
合并区间
(1) 题目解析
(2) 算法原理
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(),intervals.end());vectorvectorint res;int n intervals.size();// 取左右端点int left intervals[0][0],right intervals[0][1];for(int i1;in;i){int a intervals[i][0],b intervals[i][1];if(a right){// 有重合区间right max(right,b);}else{// 更新res.push_back({left,right});left a;right b;}}// 最后一组 区间 也需要被插入res.push_back({left,right});return res;}
};
证明 因为我们默认了排完序之后所有的左端点能合并的都是连续的。所以我们使用反证法设左端点排完序后不连续 所以我们按照左端点排完序后一旦将区间合并那么其一顶是连续的。 无重叠区间
(1) 题目解析 (2) 算法原理 class Solution {
public:int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(),intervals.end());int n intervals.size();int ret 0;int left intervals[0][0],right intervals[0][1];for(int i1;in;i){int a intervals[i][0],b intervals[i][1];if(a right){// 存在重叠 保留小范围的ret;right min(right,b);}else{// 不存在重叠 新的开始right b;}}return ret;}
};
证明: 这样的贪心策略是否正确呢 我们假设贪心解是错误的。所以我们会得到两份答案一份是贪心解一份是最有解 ⽤最少数量的箭引爆⽓球
(1) 题目解析 (2) 算法原理 class Solution {
public:int findMinArrowShots(vectorvectorint points) {sort(points.begin(),points.end());int n points.size();int left points[0][0],right points[0][1];int ret 1; // 第一个区间就需要引爆for(int i1;in;i){int a points[i][0],b points[i][1];if(a right){// 重叠的 可以一支箭引爆right min(right,b);}else{ret; // 不是重叠 需要一支箭引爆right b;}}return ret;}
}; 本篇到此结束感谢你的阅读。
祝你好运向阳而生~
