【区间贪心】合并区间 / 无重叠区间 / 用最少数量的箭引爆气球 / 俄罗斯套娃信封问题

⭐️个人主页：@小羊 ⭐️所属专栏：贪心算法 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

---

合并区间

• 合并区间

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());vector<vector<int>> ret;int left = intervals[0][0], right = intervals[0][1];for (int i = 1; i < intervals.size(); i++){int a = intervals[i][0], b = intervals[i][1];if (a <= right) right = max(right, b);else{ret.push_back({left, right});left = a, right = b;}}ret.push_back({left, right});return ret;}
};

---

无重叠区间

• 无重叠区间

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());int ret = 0, right = intervals[0][1];for (int i = 1; i < intervals.size(); i++){int a = intervals[i][0], b = intervals[i][1];if (a < right){ret++;// 删除右端点较大的区间right = min(right, b);}else right = b;}return ret;}
};

---

用最少数量的箭引爆气球

• 用最少数量的箭引爆气球

贪心策略：我们在射箭的时候，要发挥每一支箭最大的作用，应该把互相重叠的区间统一引爆。

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

---

俄罗斯套娃信封问题

• 俄罗斯套娃信封问题

动态规划解法，会超时：

class Solution {
public:int maxEnvelopes(vector<vector<int>>& e) {sort(e.begin(), e.end());int n = e.size(), ret = 0;vector<int> dp(n, 1);for (int i = 1; i < n; i++){for (int j = 0; j < i; j++)if (e[i][0] > e[j][0] && e[i][1] > e[j][1])dp[i] = max(dp[i], dp[j] + 1);ret = max(ret, dp[i]);}return ret;}
};

重写排序+贪心+二分：

class Solution {
public:int maxEnvelopes(vector<vector<int>>& e) {sort(e.begin(), e.end(), [](const vector<int>& v1, const vector<int>& v2){return v1[0] == v2[0] ? v1[1] > v2[1] : v1[0] < v2[0];});vector<int> ret;ret.push_back(e[0][1]);for (int i = 1; i < e.size(); i++){int a = e[i][1];if (a > ret.back()) ret.push_back(a);else {int left = 0, right = ret.size() - 1;while (left < right){int mid = (left + right) >> 1;if (ret[mid] < a) left = mid + 1;else right = mid;}ret[left] = a;}}return ret.size();}
};

---

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~