Leetcode刷题100天—452. 用最少数量的箭引爆气球(贪心)—day40

素颜马尾好姑娘i 2022-09-14 11:06 78阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20211007163502270][]

#### [452. 用最少数量的箭引爆气球][452.] ####

难度中等457收藏分享切换为英文接收动态反馈

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 ```x``start```，```x``end```， 且满足 ```xstart ≤ x ≤ x``end```，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 `points` ，其中 `points [i] = [xstart,xend]` ，返回引爆所有气球所必须射出的最小弓箭数。

**示例 1：**

输入：points = [[10,16],[2,8],[1,6],[7,12]]
    输出：2
    解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

**示例 2：**

输入：points = [[1,2],[3,4],[5,6],[7,8]]
    输出：4

**示例 3：**

输入：points = [[1,2],[2,3],[3,4],[4,5]]
    输出：2

**示例 4：**

输入：points = [[1,2]]
    输出：1

**示例 5：**

输入：points = [[2,3],[2,3]]
    输出：1

**提示：**

*  `1 <= points.length <= 104`
 *  `points[i].length == 2`
 *  `-231 <= xstart < xend <= 231 - 1`

package 贪心;
    
    import java.util.Arrays;
    import java.util.Comparator;
    
    /* * https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/ * 由题目可以知道，如果这些坐标有集合，那么一定会一箭射中也就是Xend>=X2start */
    public class _452_用最少数量的箭引爆气球 { 
        public int findMinArrowShots(int[][] points) { 
            if (points.length==1) { 
    			return 1;
    		}
    // 设定返回值
        	int count=0;
    // 先小到大排序
        	Arrays.sort(points, new Comparator<int[]>() { 
                public int compare(int[] point1, int[] point2) { 
                    if (point1[0] > point2[0]) { 
                        return 1;
                    } else if (point1[0] < point2[0]) { 
                        return -1;
                    } else { 
                        return 0;
                    }
                }
            });
        	
    // 获取第一个元素
        	int[] p=points[0] ;
    // 从第二个元素开始遍历判断
        	for(int i=1;i<points.length;i++) { 
    // 如果小于start，说明没有集合
        		if (p[1]<points[i][0]) { 
    				count++;
    				p=points[i];
    
    			}else { //否则就是有集合
    // 找出集合中最小的end
    				if (p[1]>points[i][1]) { 
    					p=points[i];
    				}
    			}
        	}
    // 每次遍历到最后一个count都不能++，所以要返回count+1
        	return count+1;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20211007163502270]: /images/20220828/c3d4686a3c0944968abfbe082aea0119.png
[452.]: https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/