【区间贪心】合并区间 / 无重叠区间 / 用最少数目的箭引爆气球 / 俄罗斯套娃信封问题
https://i-blog.csdnimg.cn/direct/621057c10592434099cf0e6395de3624.png ⭐️个人主页：@小羊 ⭐️所属专栏：贪心算法 很荣幸您能阅读我的文章，诚请评论辅导，欢迎欢迎 ~ https://img-blog.csdnimg.cn/direct/e678d5c05144448f9c9233bf292616a1.gif合并区间
[*]合并区间
https://i-blog.csdnimg.cn/direct/9a7670d9ad4c4d0e8efe5f23a0881577.png
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> ret;
int left = intervals, right = intervals;
for (int i = 1; i < intervals.size(); i++)
{
int a = intervals, b = intervals;
if (a <= right) right = max(right, b);
else
{
ret.push_back({left, right});
left = a, right = b;
}
}
ret.push_back({left, right});
return ret;
}
};
无重叠区间
[*]无重叠区间
https://i-blog.csdnimg.cn/direct/8e1a0834c1a7496386f59a5d7245e4c2.png
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
int ret = 0, right = intervals;
for (int i = 1; i < intervals.size(); i++)
{
int a = intervals, b = intervals;
if (a < right)
{
ret++;// 删除右端点较大的区间
right = min(right, b);
}
else right = b;
}
return ret;
}
};
用最少数目的箭引爆气球
[*]用最少数目的箭引爆气球
https://i-blog.csdnimg.cn/direct/2f42afbb00b6425891f57f99fa2547d5.png
贪心策略：我们在射箭的时间，要发挥每一支箭最大的作用，应该把互相重叠的区间统一引爆。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end());
int ret = 0, right = points;
for (int i = 1; i < points.size(); i++)
{
int a = points, b = points;
if (a <= right) right = min(right, b);
else
{
right = b;
ret++;
}
}
return ret + 1;
}
};
俄罗斯套娃信封问题
[*]俄罗斯套娃信封问题
https://i-blog.csdnimg.cn/direct/fd9c5b14c1584f8f85fbcf83de68476f.png
动态规划解法，会超时：
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 > e && e > e)
dp = max(dp, dp + 1);
ret = max(ret, dp);
}
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 == v2 ? v1 > v2 : v1 < v2;
});
vector<int> ret;
ret.push_back(e);
for (int i = 1; i < e.size(); i++)
{
int a = e;
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 < a) left = mid + 1;
else right = mid;
}
ret = a;
}
}
return ret.size();
}
};
本篇文章的分享就到这里了，假如您觉得在本文有所劳绩，还请留下您的三连支持哦~
https://img-blog.csdnimg.cn/img_convert/ef07608f8c5523995a3671f982ca95bd.jpeg
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]