Minimum Number of Arrows to Burst Balloons

How it works

Sorting by end position offers a cleaner greedy approach. By shooting an arrow at the end of the first balloon, we maximize the chance of hitting subsequent balloons. Each balloon that starts after our current arrow position requires a new arrow.

This is a classic interval scheduling pattern: always pick the earliest finishing interval first. When we shoot at the end of a balloon, any other balloon that overlaps must have started before or at that point.

Steps

1. Sort the balloons by their ending position.
2. Start with one arrow at the end of the first balloon.
3. For each subsequent balloon:
   • If it starts after the current arrow position, shoot a new arrow at this balloon's end and increment res.
   • Otherwise, the current arrow already covers this balloon.
4. Return the total arrow count.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Using Subtraction for Comparator with Large Values

When sorting intervals with coordinates that can be very large (up to 2^31 - 1) or very small (down to -2^31), using a[0] - b[0] as a comparator can cause integer overflow. For example, comparing [-2147483648, 0] with [2147483647, 0] would overflow. Always use Integer.compare(a[0], b[0]) in Java or explicit comparison operators like a[0] < b[0] in other languages.

Not Updating the Overlap Region Correctly

When merging overlapping balloons, you must shrink the overlap region by taking the minimum of the end values, not the maximum. If balloon A ends at 6 and balloon B ends at 4, the arrow must be shot at or before position 4 to hit both. Forgetting to update prevEnd = min(curr[1], prevEnd) will cause incorrect counts when a later balloon extends beyond the current overlap region.

Confusing Inclusive vs Exclusive Overlap Checks

The problem states that balloons touching at a single point can be burst by one arrow. This means the overlap check should be curr[0] <= prevEnd (inclusive), not curr[0] < prevEnd. Missing this edge case will count extra arrows for balloons that just touch at their boundaries.

from typing import List

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])
        res, prevEnd = 1, points[0][1]

        for i in range(1, len(points)):
            if points[i][0] > prevEnd:
                prevEnd = points[i][1]
                res += 1

        return res

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });
        int res = 1, prevEnd = points[0][1];

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

        return res;
    }
};