【贪心算法】（第十二篇）
目录
⽆重叠区间（medium）
题目解析
讲解算法原理
编写代码
⽤最少数量的箭引爆⽓球（medium）
题目解析
讲解算法原理
编写代码
⽆重叠区间（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个区间的集合 intervals ，其中 intervals[i] = [start(i), end(i)] 。返回需要移除区间的最⼩数量，使剩余区间互不重叠。
⽰例1:
输⼊:intervals=[[1,2],[2,3],[3,4],[1,3]]
输出:1
解释:移除[1,3]后，剩下的区间没有重叠。
⽰例2:
输⼊:intervals=[[1,2],[1,2],[1,2]]
输出:2
解释:你需要移除两个[1,2]来使剩下的区间没有重叠。
⽰例3:
输⼊:intervals=[[1,2],[2,3]]
输出:0
解释:你不需要移除任何区间，因为它们已经是⽆重叠的了。
提⽰:
◦ 1 <= intervals.length <= 10^5
◦ intervals[i].length == 2
◦ -5 * 10^4 <= start(i) < end(i) <= 5 * 10^4
讲解算法原理
解法（贪⼼）：
贪⼼策略：
a. 按照「左端点」排序；
b. 当两个区间「重叠」的时候，为了能够「在移除某个区间后，保留更多的区间」，我们应该把
「区间范围较⼤」的区间移除。
如何移除区间范围较⼤的区间：
由于已经按照「左端点」排序了，因此两个区间重叠的时候，我们应该移除「右端点较⼤」的区间
编写代码
c++算法代码：
class Solution
{
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals)
{
// 1. 按照左端点排序
sort(intervals.begin(), intervals.end());
// 2. 移除区间
int ret = 0;
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) // 有重叠部分
{
ret++; // 删掉⼀个区间
right = min(right, b);
}
else // 没有重叠部分
{
right = b;
}
}
return ret;
}
};java算法代码：
class Solution
{
public int eraseOverlapIntervals(int[][] intervals)
{
// 1. 按照左端点排序
Arrays.sort(intervals, (v1, v2) ->
{
return v1[0] - v2[0];
});
// 2. 移除区间
int ret = 0;
int left = intervals[0][0], right = intervals[0][1];
for(int i = 1; i < intervals.length; i++)
{
int a = intervals[i][0], b = intervals[i][1];
if(a < right) // 有重叠区间
{
ret++;
right = Math.min(right, b); // 贪⼼：删除右端点较⼤的区间 }
else // 没有重叠区间
{
right = b;
}
}
return ret;
}
}⽤最少数量的箭引爆⽓球（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
有⼀些球形⽓球贴在⼀堵⽤XY平⾯表⽰的墙⾯上。墙⾯上的⽓球记录在整数数组 points ，其中
points[i] = [x(start), x(end)] 表⽰⽔平直径在 x(start) 和 x(end) 之间的⽓球。
你不知道⽓球的确切y坐标。
⼀⽀⼸箭可以沿着x轴从不同点完全垂直地射出。在坐标 x 处射出⼀⽀箭，若有⼀个⽓球的直径的开始和结束坐标为 x (start)， x (end)且满⾜ x(start) ≤ x ≤ x(end) ，则该⽓球会被引爆。可以射出的⼸箭的数量没有限制。⼸箭⼀旦被射出之后，可以⽆限地前进。
给你⼀个数组 points ，返回引爆所有⽓球所必须射出的最⼩⼸箭数。
⽰例1：
输⼊：points=[[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：⽓球可以⽤2⽀箭来爆破:
-在x=6处射出箭，击破⽓球[2,8]和[1,6]。
-在x=11处发射箭，击破⽓球[10,16]和[7,12]。
⽰例2：
输⼊：points=[[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个⽓球需要射出⼀⽀箭，总共需要4⽀箭。
⽰例3：
输⼊：points=[[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：⽓球可以⽤2⽀箭来爆破:
-在x=2处发射箭，击破⽓球[1,2]和[2,3]。
-在x=4处射出箭，击破⽓球[3,4]和[4,5]。
提⽰:
◦ 1 <= points.length <= 10^5
◦ points[i].length == 2
◦ -2^31 <= x(start) < x(end) <= 2^31 - 1
讲解算法原理
解法（贪⼼）：
贪⼼策略：
a. 按照左端点排序，我们发现，排序后有这样⼀个性质：「互相重叠的区间都是连续的」；b. 这样，我们在射箭的时候，要发挥每⼀⽀箭「最⼤的作⽤」，应该把「互相重叠的区间」统⼀
引爆。
如何求互相重叠区间？
由于我们是按照「左端点」排序的，因此对于两个区间，我们求的是它们的「交集」：a. 左端点为两个区间左端点的「最⼤值」（但是左端点不会影响我们的合并结果，所以可以忽略）；
b. 右端点为两个区间右端点的「最⼩值」。
编写代码
c++算法代码：
class Solution
{
public:
int findMinArrowShots(vector<vector<int>>& points)
{
// 1. 按照左端点排序
sort(points.begin(), points.end());
// 2. 求互相重叠区间的数量
int right = points[0][1];
int ret = 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 // ⽆重叠部分
{
ret++;
right = b;
}
}
return ret;
}
};java算法代码：
class Solution
{
public int findMinArrowShots(int[][] points)
{
// 1. 按照左端点排序
Arrays.sort(points, (v1, v2) ->
{
return v1[0] > v2[0] ? 1 : -1;
});
// 2. 求出互相重叠的区间的数量
int right = points[0][1];
int ret = 1;
for(int i = 1; i < points.length; i++)
{
int a = points[i][0], b = points[i][1];
if(a <= right) // 有重叠
{
right = Math.min(right, b);
}
else // 没有重叠
{
ret++;
right = b;
}
}
return ret;
}
}