题目描述：

LeetCode 452. Minimum Number of Arrows to Burst Balloons

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 10⁴ balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_end bursts by an arrow shot at x if x_start ≤ x ≤ x_end. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

题目大意：

二维空间中有一组气球。对于每一个气球，输入其水平直径的起止点坐标。由于是水平的，不需要考虑y坐标，因而用x坐标表示起止点即可。起点总是小于终点。最多10^4个气球。

一支箭从x轴的不同点竖直射出。某气球的起止点坐标为xstart和xend，当xstart ≤ x ≤ xend时，该气球会被射中。射出的弓箭数目没有限制。弓箭可以保持无限移动。计算最少需要多少弓箭可以将所有气球射中。

解题思路：

贪心算法（Greedy Algorithm）

按照气球的起点排序

变量emin记录当前可以一箭命中的气球终点坐标的最小值，初始化为+∞

遍历排序后的气球起始点坐标s, e

若emin < s，说明当前气球无法用一支箭射中，则令最终结果ans + 1，令emin=+∞

更新emin = min(emin, e)

Python代码：

class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        ans = 0
        emin = MAXINT = 0x7FFFFFFF
        for s, e in sorted(points):
            if emin < s:
                ans += 1
                emin = MAXINT
            emin = min(emin, e)
        return ans + bool(points)

 

本文链接：http://bookshadow.com/weblog/2016/11/06/leetcode-minimum-number-of-arrows-to-burst-balloons/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码