力扣452题（用最少的箭戳爆气球，贪心算法、暂时未解）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

452.在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

1. 很直观的想法就是气球重叠的越多，所用的弓箭数就越少，找到某一个位置，尽可能让气球重叠一起射，这就是贪心所在，使得全局使用的弓箭数最少。那么如何让气球尽可能重叠然后一起射爆呢，可以先将所有的气球进行排序，遍历每个气球，如果当前气球的左边界比前一个气球的右边界小的话，则说明这两个气球可以归为一组用一个弓箭射爆，将当前气球的右边界更新为这两个气球中的最小右边界，记录归为一组的气球的最小右边界（也就是用一个弓箭能够射爆这组气球的位置），用于给下一个气球进行比较；如果当前气球的左边界比前一个
   气球的最小右边界大的话，那么这两个气球肯定是不能用同一支弓箭射爆的，所以所需弓箭数需要加1。
2. 代码如下，由于使用qsort函数对二维数组排序不是很熟，所以这里暂时还有个问题没解决，在IDE上可以通过，但是在leetcode上过不了，后续有空再进行修改。

// 比较函数，用于对气球进行排序
int cmp_int(const void* _a , const void* _b) {
    return (*(int**)_a)[0] - (*(int**)_b)[0];
}

int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
	// 对气球按起始坐标进行排序
    qsort(points, pointsSize, sizeof(int*), cmp_int);
    if (pointsSize == 0) //没有气球就不需要弓箭
        return 0;
    *pointsColSize = 2;
    int res = 1; //有气球的话至少需要一支弓箭
    for (int i = 1; i < pointsSize; i++) {
    	// 如果某个气球的左边界大于前面一组重叠气球的最小右边界，这需要弓箭数要加1
        if (points[i][0] > points[i - 1][1]) 
            res++;
        else  // 如果当前气球的左边界不大于前面一组重叠气球的最小右边界的话，说明当前气球跟前面一组重叠气球也是重叠的，更新这一组重叠气球的最小右边界确保能够用一支弓箭射爆这一组气球
            points[i][1] = points[i - 1][1] >= points[i][1] ? points[i][1] : points[i - 1][1];
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21