【贪婪算法】（第十二篇）

目次

⽆重叠区间（medium）
标题分析
解说算法原理
编写代码
⽤最少数目的箭引爆⽓球（medium）
标题分析
解说算法原理
编写代码

---

⽆重叠区间（medium）

标题分析

1.标题链接：. - 力扣（LeetCode）
2.标题形貌
   给定⼀个区间的聚集 intervals ，此中 intervals = [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.length == 2
◦ -5 * 10^4 <= start(i) < end(i) <= 5 * 10^4
  解说算法原理

解法（贪⼼）：
贪⼼计谋：
a. 按照「左端点」排序；
b. 当两个区间「重叠」的时间，为了可以大概「在移除某个区间后，生存更多的区间」，我们应该把
「区间范围较⼤」的区间移除。
怎样移除区间范围较⼤的区间：
由于已经按照「左端点」排序了，因此两个区间重叠的时间，我们应该移除「右端点较⼤」的区间
编写代码

c++算法代码：

1. class Solution
2. {
3. public:
4. int eraseOverlapIntervals(vector<vector<int>>& intervals)
5. {
6. // 1. 按照左端点排序
7. sort(intervals.begin(), intervals.end());
8. // 2. 移除区间
9. int ret = 0;
10. int left = intervals[0][0], right = intervals[0][1];
11. for(int i = 1; i < intervals.size(); i++)
12. {
13. int a = intervals[i][0], b = intervals[i][1];
14. if(a < right) // 有重叠部分
15. {
16. ret++; // 删掉⼀个区间
17. right = min(right, b);
18. }
19. else // 没有重叠部分
20. {
21. right = b;
22. }
23. }
24. return ret;
25. }
26. };

复制代码

java算法代码：

1. class Solution
2. {
3. public int eraseOverlapIntervals(int[][] intervals)
4. {
5. // 1. 按照左端点排序
6. Arrays.sort(intervals, (v1, v2) ->
7. {
8. return v1[0] - v2[0];
9. });
10. // 2. 移除区间
11. int ret = 0;
12. int left = intervals[0][0], right = intervals[0][1];
13. for(int i = 1; i < intervals.length; i++)
14. {
15. int a = intervals[i][0], b = intervals[i][1];
16. if(a < right) // 有重叠区间
17. {
18. ret++;
19. right = Math.min(right, b); // 贪⼼：删除右端点较⼤的区间 }
20. else // 没有重叠区间
21. {
22. right = b;
23. }
24. }
25. return ret;
26. }
27. }

复制代码

⽤最少数目的箭引爆⽓球（medium）

标题分析

1.标题链接：. - 力扣（LeetCode）
2.标题形貌
   有⼀些球形⽓球贴在⼀堵⽤XY平⾯表⽰的墙⾯上。墙⾯上的⽓球纪录在整数数组 points ，此中
points = [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.length == 2
◦ -2^31 <= x(start) < x(end) <= 2^31 - 1
  解说算法原理

解法（贪⼼）：
贪⼼计谋：
a. 按照左端点排序，我们发现，排序后有如许⼀个性子：「相互重叠的区间都是一连的」；b. 如许，我们在射箭的时间，要发挥每⼀⽀箭「最⼤的作⽤」，应该把「相互重叠的区间」统⼀
引爆。
怎样求相互重叠区间？
由于我们是按照「左端点」排序的，因此对于两个区间，我们求的是它们的「交集」：a. 左端点为两个区间左端点的「最⼤值」（但是左端点不会影响我们的归并结果，以是可以忽略）；
b. 右端点为两个区间右端点的「最⼩值」。
编写代码

c++算法代码：

1. class Solution
2. {
3. public:
4. int findMinArrowShots(vector<vector<int>>& points)
5. {
6. // 1. 按照左端点排序
7. sort(points.begin(), points.end());
8. // 2. 求互相重叠区间的数量
9. int right = points[0][1];
10. int ret = 1;
11. for(int i = 1; i < points.size(); i++)
12. {
13. int a = points[i][0], b = points[i][1];
14. if(a <= right) // 有重叠部分
15. {
16. right = min(right, b);
17. }
18. else // ⽆重叠部分
19. {
20. ret++;
21. right = b;
22. }
23. }
24. return ret;
25. }
26. };

复制代码

java算法代码：

1. class Solution
2. {
3. public int findMinArrowShots(int[][] points)
4. {
5. // 1. 按照左端点排序
6. Arrays.sort(points, (v1, v2) ->
7. {
8. return v1[0] > v2[0] ? 1 : -1;
9. });
10. // 2. 求出互相重叠的区间的数量
11. int right = points[0][1];
12. int ret = 1;
13. for(int i = 1; i < points.length; i++)
14. {
15. int a = points[i][0], b = points[i][1];
16. if(a <= right) // 有重叠
17. {
18. right = Math.min(right, b);
19. }
20. else // 没有重叠
21. {
22. ret++;
23. right = b;
24. }
25. }
26. return ret;
27. }
28. }

复制代码