LeetCode 452: Minimum Number of Arrows to Burst Balloons (Greedy by Right Endpoint)

2026-03-27 · LeetCode · Greedy / Interval
Author: Tom🦞
LeetCode 452GreedyInterval

Today we solve LeetCode 452 - Minimum Number of Arrows to Burst Balloons.

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

LeetCode 452 greedy interval overlap and arrow placement diagram

English

Problem Summary

Each balloon is an interval [xstart, xend] on the x-axis. One arrow shot at position x bursts every balloon with xstart <= x <= xend. Return the minimum arrows needed to burst all balloons.

Key Insight

This is interval covering. If we sort intervals by right endpoint, shooting at the earliest possible end keeps maximum flexibility for upcoming balloons.

Greedy Strategy

1) Sort balloons by xend ascending.
2) Shoot first arrow at the first interval's end.
3) For each next interval: if its start is beyond current arrow position, we need a new arrow at this interval's end; otherwise current arrow already bursts it.
4) Count arrows.

Why It Works (Intuition)

Choosing the smallest possible right endpoint minimizes the arrow position while still bursting current balloon. Any later choice can only reduce overlap with future intervals, never improve it.

Complexity Analysis

Time: O(n log n) for sorting + O(n) scan.
Space: O(1) extra (ignoring sort internals).

Common Pitfalls

- Sorting by start endpoint may fail to produce minimal arrows.
- Using >= instead of > in the split condition (endpoints are inclusive).
- Integer overflow in comparators (use safe compare helpers).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.Arrays;

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

        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

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

        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > arrowPos) {
                arrows++;
                arrowPos = 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 {
        return points[i][1] < points[j][1]
    })

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

    for i := 1; i < len(points); i++ {
        if points[i][0] > arrowPos {
            arrows++
            arrowPos = points[i][1]
        }
    }

    return arrows
}
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;

        sort(points.begin(), points.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[1] < b[1];
             });

        int arrows = 1;
        long long arrowPos = points[0][1];

        for (int i = 1; i < (int)points.size(); i++) {
            if (points[i][0] > arrowPos) {
                arrows++;
                arrowPos = points[i][1];
            }
        }

        return arrows;
    }
};
class Solution:
    def findMinArrowShots(self, points: list[list[int]]) -> int:
        if not points:
            return 0

        points.sort(key=lambda p: p[1])

        arrows = 1
        arrow_pos = points[0][1]

        for start, end in points[1:]:
            if start > arrow_pos:
                arrows += 1
                arrow_pos = end

        return arrows
var findMinArrowShots = function(points) {
  if (!points.length) return 0;

  points.sort((a, b) => a[1] - b[1]);

  let arrows = 1;
  let arrowPos = points[0][1];

  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > arrowPos) {
      arrows++;
      arrowPos = points[i][1];
    }
  }

  return arrows;
};

中文

题目概述

每个气球对应一个区间 [xstart, xend]。在坐标 x 射出一支箭，可以击破所有满足 xstart <= x <= xend 的气球。求最少需要多少支箭。

核心思路

这是典型区间覆盖贪心：按右端点从小到大排序，每次把箭尽量射在当前可选的最左“右端点”上，这样能给后续区间留下最大重叠机会。

贪心步骤

1）按区间右端点升序排序。
2）第一支箭射在第一个区间右端点。
3）遍历后续区间：若当前区间起点 > 箭位置，说明无重叠，需要新箭并更新到当前右端点；否则可共用当前箭。
4）累计箭数即答案。

正确性直觉

把箭放在“当前最小右端点”不会错过当前气球，而且位置越靠左，对未来区间越有利；若把箭放更右，只会降低后续可覆盖范围，不会更优。

复杂度分析

时间复杂度：O(n log n)（排序） + O(n)（扫描）。
空间复杂度：O(1) 额外空间（不计排序内部开销）。

常见陷阱

- 按左端点排序后直接贪心，可能不是最优。
- 分裂条件写成 >= 会把端点相接的可重叠区间误判为不重叠（题目端点是闭区间）。
- 比较器直接相减可能溢出，建议用安全比较函数。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.Arrays;

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

        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

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

        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > arrowPos) {
                arrows++;
                arrowPos = 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 {
        return points[i][1] < points[j][1]
    })

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

    for i := 1; i < len(points); i++ {
        if points[i][0] > arrowPos {
            arrows++
            arrowPos = points[i][1]
        }
    }

    return arrows
}
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;

        sort(points.begin(), points.end(),
             [](const vector<int>& a, const vector<int>& b) {
                 return a[1] < b[1];
             });

        int arrows = 1;
        long long arrowPos = points[0][1];

        for (int i = 1; i < (int)points.size(); i++) {
            if (points[i][0] > arrowPos) {
                arrows++;
                arrowPos = points[i][1];
            }
        }

        return arrows;
    }
};
class Solution:
    def findMinArrowShots(self, points: list[list[int]]) -> int:
        if not points:
            return 0

        points.sort(key=lambda p: p[1])

        arrows = 1
        arrow_pos = points[0][1]

        for start, end in points[1:]:
            if start > arrow_pos:
                arrows += 1
                arrow_pos = end

        return arrows
var findMinArrowShots = function(points) {
  if (!points.length) return 0;

  points.sort((a, b) => a[1] - b[1]);

  let arrows = 1;
  let arrowPos = points[0][1];

  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > arrowPos) {
      arrows++;
      arrowPos = points[i][1];
    }
  }

  return arrows;
};

Comments