当前位置：首页 > news >正文

day31贪心算法用最少数量的箭引爆气球和无重叠区间

news 2025/8/15 20:08:33

题目描述
在这里插入图片描述
题目分析：

x轴向上射箭，12一支，重叠的需要一支，3-8一支，7-16一支返回2；
就是让重叠的气球尽量在一起，局部最优；用一支弓箭，全局最优就是最少弓箭；
如何去寻找重叠的气球？和记录弓箭数？
1.对所有气球排序；（左边界排序如上图）；
2. if 如果第i个气球的左边界大于第i-1个气球的右边界；即point[i][0] > point[i-1][1] 比如上图中3 6 的左边界3大于右边界1 2 的右边界2；那么弓箭数++；
3.else 就是重叠右边界取最小值；
在这里插入图片描述
如图36 48重叠，右边界取6 8 的最小值6作为重叠的右边界；
else 逻辑: a: 更新右边界；points[i][1] = min(points[i-1][1] ,points[i][1] );
b:拿这个右边界和下一个气球比较；

int cmp(const void *a, const void *b)
{int *x = *(int **)a;int *y = *(int **)b;if (x[0] == y[0]) {return x[1] > y[1];}return x[0] > y[0];
}int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){//将points数组作升序排序qsort(points, pointsSize, sizeof(points[0]),cmp);int arrowNum = 1;int i = 1;for(i = 1; i < pointsSize; i++) {//若前一个气球与当前气球不重叠，证明需要增加箭的数量if(points[i][0] > points[i-1][1])arrowNum++;else//若前一个气球与当前气球重叠，判断并更新最小的x_endpoints[i][1] = fmin(points[i-1][1] ,points[i][1] );}return arrowNum;
}

题目描述
在这里插入图片描述
分析：
左边界排序，
if nums[i][0] >= nums[i-1][1] i的左边界大于i-1的右边界表示没有重叠；
else 重叠 cnt++；右边界也是取最小值，和上一题一样； nums[i][1] = min(nums[i-1][1],nums[i][1]);

代码一

int cmp(const void *a, const void *b)
{int *x = *(int **)a;int *y = *(int **)b;if (x[0] == y[0]) {return x[1] > y[1];}return x[0] > y[0];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){// 贪心算法if (intervalsSize == 0) {return 0;}// end递增排序qsort(intervals, intervalsSize, sizeof(int *),cmp);int count = 0;for (int i = 1; i < intervalsSize; i++) { // i 和 i-1if (intervals[i][0] < intervals[i-1][1]) {//重叠count++;//后面区间和当前区间是否重叠 更新右边界intervals[i][1] = fmin(intervals[i][1], intervals[i-1][1]);}}// 返回重复区间数return count;
}

代码二

int cmp(const void *pa, const void *pb)
{return (*(int**)pa)[1] - (*(int**)pb)[1];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){// 贪心算法if (intervalsSize == 0) {return 0;}// end递增排序qsort(intervals, intervalsSize, sizeof(int*), cmp);int x_end = intervals[0][1];int start;int count = 1;for (int i = 1; i < intervalsSize; i++) {start = intervals[i][0];if (start >= x_end) {// 不相交count++;// 更新不重复区间endx_end = intervals[i][1];}}// 返回重复区间数return intervalsSize - count;
}