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

Categories:

题目描述
思路分析
1. 解法一：贪心排序（推荐）
相似题目

题目描述

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

思路分析

解法一：贪心排序（推荐）

核心思路：

按区间右端点从小到大排序。

维护当前箭的覆盖右边界，若新区间起点大于边界，则需要新箭。

用最少箭数覆盖所有区间。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示区间数量。

空间复杂度：O(1)，排序额外空间视实现而定。

import java.util.*;

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }

        // 按右端点排序，贪心选择最早结束的气球
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1;
        int end = points[0][1];

        // 扫描区间并统计箭数
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                arrows++;
                end = points[i][1];
            }
        }

        return arrows;
    }
}

import "sort"

func findMinArrowShots(points [][]int) int {
	if len(points) == 0 {
		return 0
	}

	// 按右端点排序，贪心选择最早结束的气球
	sort.Slice(points, func(i, j int) bool {
		if points[i][1] == points[j][1] {
			return points[i][0] < points[j][0]
		}
		return points[i][1] < points[j][1]
	})

	arrows := 1
	end := points[0][1]

	// 扫描区间并统计箭数
	for i := 1; i < len(points); i++ {
		if points[i][0] > end {
			arrows++
			end = points[i][1]
		}
	}

	return arrows
}

相似题目

题目	难度	考察点
56. 合并区间	中等	区间排序
57. 插入区间	中等	区间处理
435. 无重叠区间	中等	贪心
253. 会议室 II	中等	贪心、堆
986. 区间列表的交集	中等	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/90181331