Minimum Number of Arrows to Burst Balloons-K6K4.com

原题： https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/description/

题意： 二维空间中有一组气球。对于每一个气球，输入其水平直径的起止点坐标。由于是水平的，不需要考虑y坐标，因而用x坐标表示起止点即可。起点总是小于终点。最多10^4个气球。一支箭从x轴的不同点竖直射出。某气球的起止点坐标为xstart和xend，当xstart ≤ x ≤ xend时，该气球会被射中。射出的弓箭数目没有限制。弓箭可以保持无限移动。计算最少需要多少弓箭可以将所有气球射中。

例子：

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

输出:2

说明:一种方法是在x = 6（例如射中气球[2,8]和[1,6]）处射出一支箭和在x = 11处射出另一支箭（射中另外两个气球）。

标签：气球、射中、起止点、弓箭、坐标、面试

猜你感兴趣的圈子：

LeetCode交流圈

星空

2017-08-18 17:47:17 1楼#1层

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)

星空

2017-08-18 17:48:01 2楼#1层

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        Arrays.sort(points, (a, b) -> a[1] - b[1]);
        int arrowPos = points[0][1];
        int arrowCnt = 1;
        for (int i = 1; i < points.length; i++) {
            if (arrowPos >= points[i][0]) {
                continue;
            }
            arrowCnt++;
            arrowPos = points[i][1];
        }
        return arrowCnt;
    }
}

星空

2017-08-18 17:49:40 3楼#1层

class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        points = sorted(points, key = lambda x: x[1])
        res, end = 0, -float('inf')
        for interval in points:
            if interval[0] > end:
                res += 1
                end = interval[1]
        return res

取消

回复

推荐圈子

LeetCode交流圈