技术

leetcode 452.用最少的箭引爆气球

image-20201116234520178

解题思路

  1. 贪心算法的核心就是先排序再遍历处理；
  2. 排序使用qsort函数
  3. 对于排序后的数组，一个简单的规则就是以第0个气球为[start,end]范围，
  4. 如果后面气球的起始小于end,则可以一枪解决；并更新start
  5. 如果后面气球的起始大于end，那肯定要再开一枪，并更新新的[start, end];

复杂度分析

  • 时间复杂度 O（nlogn）
  • 空间复杂度 O（1）

    代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#define MAX(x, y) ((x >= y) ? x : y)
#define LEN 1000
int cmpFunc(const void *a, const void *b) {
    return (((int**)a)[0][1] > ((int **)b)[0][1]);
}

int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){
    if (points == NULL || pointsSize == 0) return 0;

    qsort(points, pointsSize, sizeof(points[0]), cmpFunc);
    
    int start = points[0][0];
    int end = points[0][1];
    int cnt = 1;
    for (int i = 1; i < pointsSize; i++) {
        if (end >= points[i][0]) {
            start = MAX(start, points[i][0]);
            continue;
        } else {
            cnt++;
            start = points[i][0];
            end = points[i][1];
        }
    }
    return cnt;
}