esc to dismiss

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

题目

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

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

给你一个数组 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

解体思路

这道题目题解用 排序 + 贪心算法

如果不排序,那么遍历会超时。

有两种排序方式:对于气球的起止横坐标 [start, end], 可以先根据 start 排序,再根据 end 排序;还有一种方式是仅对 end 排序,我们看第二种:

对气球 end 排序后,只需要从第一个气球(end 最小)开始比较,如果 start 小于等于 end,则说明这个气球可以同时被穿;否则需要增加一箭,依次类推。

type point struct {
    start, end int
}

type byEnd []*point

func (b byEnd) Len() int {
    return len(b)
}

func (b byEnd) Less(i, j int) bool {
    return b[i].end < b[j].end
}

func (b byEnd) Swap(i, j int) {
    b[i], b[j] = b[j], b[i]
}

func findMinArrowShots(points [][]int) int {
    size := len(points)
    allPoints := make([]point, size, size)
    ps := make([]*point, size, size)
    for i, p := range points {
        allPoints[i].start = p[0]
        allPoints[i].end = p[1]
        ps[i] = &allPoints[i]
    }

    sort.Sort(byEnd(ps))

    var arrow *point
    count := 0
    for _, p := range ps {
        if arrow == nil || p.start > arrow.end {
            arrow = p
            count++
        }
    }
    return count
}

经验教训

  1. 排序
  2. go 的排序可以用 sort 包,但需要实现 Len, Less, Swap 三个方法。
x