LeetCode0452.用最少数量的箭引爆气球【Medium】【Python】【区问题】Leetnumberof在二维空间中。对于每个气球，提供的输入是水平直径的开始和结束坐标。由于它是水平的，y坐标无关紧要，因此直径的起点和终点的x坐标就足够了。开始总是小于结束。最多会有10^4个气球。可以从x轴上的不同点垂直射出一支箭。如果xstart≤x≤xend，则带有xstart和xend的气球会被射向x的箭头爆裂。可以射出的箭的数量没有限制。一支箭一旦射出，便会无限向上。问题是要找到使所有气球爆裂所必须射出的最少箭数。示例：输入：[[10,16]、[2,8]、[1,6]、[7,12]]输出：2说明：一种方法是拍摄一个例如在x=6处的箭头（使气球[2,8]和[1,6]爆裂）和在x=11处的另一个箭头（使另外两个气球爆裂）。问题是有很多个球形的Balloon对于每个气球，提供的输入是气球直径在水平方向的起点和终点坐标。因为它是水平的，所以y坐标无关紧要，所以只知道开始和结束x坐标就足够了。起始坐标总是小于结束坐标。飞机上最多有10^4个气球。弓箭可以从x轴上的不同点完美地垂直射出。在坐标x处射箭，如果有一个气球的直径起点和终点在坐标xstart，xend，且满足xstart≤x≤xend，则气球会被引爆。可以射出的弓的数量没有限制。弓箭一旦射出，便可以无限前进。我们想找到引爆所有气球所需的最少弓箭数量。示例：输入：[[10,16],[2,8],[1,6],[7,12]]输出：2解释：对于这个例子，我们可以在x=6处射击（爆炸[2,8],[1,6]两个气球）和x=11（爆破另外两个气球）。idea区间是贪心的，先把右端点从小到大排序，然后temp_pos指针指向第一组右端点。每次都将temp_pos与当前的左端点进行比较。如果temp_pos<左端点，说明需要添加箭头，然后更新temp_pos为当前右端点，继续比较。时间复杂度：O(len(points))空间复杂度：O(1)PythoncodeclassSolution(object):deffindMinArrowShots(self,points):""":typepoints:List[List[int]]:rtype:int"""ifnotpointsorlen(points)==0:return0points.sort(key=lambdax:x[1])#按右端点从小到大排序temp_pos=points[0][1]cnt=1foriinrange(len(points)):iftemp_pos>=points[i][0]:#当右端点<左端点时，再添加一个箭头continuetemp_pos=points[i][1]cnt+=1返回cnt代码地址GitHub链接
