贪心算法（7）

大家好，欢迎来到IT知识分享网。

贪心算法练习记录：

leetcode 452 https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/

题目描述：

用最少数量的箭引爆气球，一个区间代表一个气球，现有一个区间集合（二维数组），如果要戳破这些气球最少需要多少箭呢？（箭只能朝着一个方向前进）

思路：

和前面记录的贪心算法（5）一样对二维数组排序（按照区间起始值大小顺序排序），排序完成后只要有区间重叠的用一根箭就可以引爆气球，维护一个左右值表示区间的重叠区间，循环遍历各个区间（二维数组中的一维数组），只要不重叠计数加一得到最少得箭。（如果每次循环时如果判断当前区间的起始值与重叠区间的右值的情况，只需要维护一个右值就行）。

代码实现：

C语言代码实现

#include<stdio.h> #include<stdlib.h> int comp(const void* a, const void* b) { int *m = *(int **)a; int *n = *(int **)b; return m[0] < n[0] ? -1 : 1; // if ((*(int**)a)[0] < (*(int**)b)[0]) // { return -1; } // return 1; } int findMinArrowShots( int** points, int pointsSize, int* pointsColSize) { if (pointsSize == 1) { return 1; } qsort(points, pointsSize, sizeof(points[0]), comp); int i=1,count = 1; bool flag = false; int start = points[0][1]; while(i<pointsSize-1 ) { if(points[i][0]>start) { start = points[i][1]; count++; i++; } else if (points[i][0] <start) { if(points[i][1]<start || points[i][0] == start) { start = points[i][1]; } i++; } } if (points[pointsSize-1][0]>start ) { count++; } return count; } int main() { int row =8; int ** a = ( int**)malloc(sizeof( int*)*row); for ( int i = 0;i<row;i++) { ( int *)a[i] = ( int*)malloc(sizeof( int)*2); } a[0][0] = 4; a[0][1] = 12; a[1][0] = 7; a[1][1] = 8; a[2][0] = 7; a[2][1] = 9; a[3][0] = 7; a[3][1] = 9; a[4][0] = 2; a[4][1] = 8; a[5][0] = 6; a[5][1] = 7; a[6][0] = 5; a[6][1] = 14; a[7][0] = 4; a[7][1] = 13; int result = findMinArrowShots(a,row,( int*)2); printf("%d" ,result); for ( int i = 0; i<row; i++) { free(a[i]); } free(a); }

采坑点：

区间可以是负数，负数减去正数就溢出了，所以使用qsort函数时应用如下方式：

 int *m = *(int **)a; int *n = *(int **)b; return m[0] < n[0] ? -1 : 1; // if ((*(int**)a)[0] < (*(int**)b)[0]) // { return -1; } // return 1;

使用以下方式会出错：

 if ((*(int**)a)[0] == (*(int**)b)[0]) return (*(int**)a)[1] - (*(int**)b)[1];//此处则表示先按第一项排序，第一项相同的情况下按第二项 return (*(int**)a)[0] - (*(int**)b)[0];