【区间贪心】合并区间 / 无重叠区间 / 用最少数目的箭引爆气球 / 俄罗斯套 ...

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

  

---

合并区间

• 合并区间
  

1. class Solution {
2. public:
3.     vector<vector<int>> merge(vector<vector<int>>& intervals) {
4.         sort(intervals.begin(), intervals.end());
5.         vector<vector<int>> ret;
6.         int left = intervals[0][0], right = intervals[0][1];
7.         for (int i = 1; i < intervals.size(); i++)
8.         {
9.             int a = intervals[i][0], b = intervals[i][1];
10.             if (a <= right) right = max(right, b);
11.             else
12.             {
13.                 ret.push_back({left, right});
14.                 left = a, right = b;
15.             }
16.         }
17.         ret.push_back({left, right});
18.         return ret;
19.     }
20. };

复制代码

---

无重叠区间

• 无重叠区间
  

1. class Solution {
2. public:
3.     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
4.         sort(intervals.begin(), intervals.end());
5.         int ret = 0, right = intervals[0][1];
6.         for (int i = 1; i < intervals.size(); i++)
7.         {
8.             int a = intervals[i][0], b = intervals[i][1];
9.             if (a < right)
10.             {
11.                 ret++;// 删除右端点较大的区间
12.                 right = min(right, b);
13.             }
14.             else right = b;
15.         }
16.         return ret;
17.     }
18. };

复制代码

---

用最少数目的箭引爆气球

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

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

1. class Solution {
2. public:
3.     int findMinArrowShots(vector<vector<int>>& points) {
4.         sort(points.begin(), points.end());
5.         int ret = 0, right = points[0][1];
6.         for (int i = 1; i < points.size(); i++)
7.         {
8.             int a = points[i][0], b = points[i][1];
9.             if (a <= right) right = min(right, b);
10.             else
11.             {
12.                 right = b;
13.                 ret++;
14.             }
15.         }
16.         return ret + 1;
17.     }
18. };

复制代码

---

俄罗斯套娃信封问题

• 俄罗斯套娃信封问题
  

动态规划解法，会超时：

1. class Solution {
2. public:
3.     int maxEnvelopes(vector<vector<int>>& e) {
4.         sort(e.begin(), e.end());
5.         int n = e.size(), ret = 0;
6.         vector<int> dp(n, 1);
7.         for (int i = 1; i < n; i++)
8.         {
9.             for (int j = 0; j < i; j++)
10.                 if (e[i][0] > e[j][0] && e[i][1] > e[j][1])
11.                     dp[i] = max(dp[i], dp[j] + 1);
12.             ret = max(ret, dp[i]);
13.         }
14.         return ret;
15.     }
16. };

复制代码

重写排序+贪心+二分：

1. class Solution {
2. public:
3.     int maxEnvelopes(vector<vector<int>>& e) {
4.         sort(e.begin(), e.end(), [](const vector<int>& v1, const vector<int>& v2){
5.             return v1[0] == v2[0] ? v1[1] > v2[1] : v1[0] < v2[0];
6.         });
7.         vector<int> ret;
8.         ret.push_back(e[0][1]);
9.         for (int i = 1; i < e.size(); i++)
10.         {
11.             int a = e[i][1];
12.             if (a > ret.back()) ret.push_back(a);
13.             else
14.             {
15.                 int left = 0, right = ret.size() - 1;
16.                 while (left < right)
17.                 {
18.                     int mid = (left + right) >> 1;
19.                     if (ret[mid] < a) left = mid + 1;
20.                     else right = mid;
21.                 }
22.                 ret[left] = a;
23.             }
24.         }
25.         return ret.size();
26.     }
27. };

复制代码

---

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。