Minimum Number of Arrows to Burst Balloons

Link

Description

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

• Input: points = [[10,16],[2,8],[1,6],[7,12]]
• Output: 2
• Explanation: The balloons can be burst by 2 arrows:
  • Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
  • Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

• Input: points = [[1,2],[3,4],[5,6],[7,8]]
• Output: 4
• Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

• Input: points = [[1,2],[2,3],[3,4],[4,5]]
• Output: 2
• Explanation: The balloons can be burst by 2 arrows:
  • Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
  • Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

• 1 <= points.length <= 10^5
• points[i].length == 2
• -2^31 <= xstart < xend <= 2^31 - 1

Solution

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](vector<int>& lhs, vector<int>& rhs) {
            return lhs[1] < rhs[1];
        });

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

• Time complexity: \(O(n\log n)\);
• Space complexity: \(O(\log n)\) for sort.

Algorithm Steps:

1. Sorting Balloons by End Coordinate:
   • The balloons are first sorted based on their end coordinates in ascending order. This is done with the sort function using a custom comparator.
   • Sorting by end coordinate ensures that we always consider shooting an arrow at the earliest possible position to burst the current balloon and potentially others.
2. Greedy Choice:
   • The core idea of the greedy approach is to shoot an arrow at the end coordinate of the first balloon. Since the balloons are sorted by their end coordinates, this choice ensures that we can burst as many balloons as possible with a single arrow.
   • The variable right keeps track of the current position where an arrow is shot. Initially, it's set to the end coordinate of the first balloon (points[0][1]).
3. Iterating Through Balloons:
   • The algorithm then iterates through the rest of the balloons. For each balloon, it checks if the start coordinate of the current balloon (points[i][0]) is greater than right.
   • If points[i][0] > right, it means the current balloon cannot be burst by the arrow shot at right, so we need to shoot another arrow. This is where the greedy choice is applied again by updating right to the end coordinate of the current balloon (points[i][1]), and incrementing the count of arrows (res).
4. Counting Arrows:
   • The variable res keeps count of the minimum number of arrows required. It's initialized to 1 because we always need at least one arrow to start with (for the first balloon).
   • Each time a new arrow is needed (when the start of the current balloon is beyond right), res is incremented.