Problem Statement

You are given an array of points where points[i] = [x_start, x_end] represents the starting and ending coordinates of the ith balloon. Balloons can be burst by shooting an arrow through any point in their range. You want to shoot the minimum number of arrows to burst all balloons.

Return the minimum number of arrows that must be shot to burst all balloons.

Examples

Example 1:

Input: points = [
                 [10, 16],
                 [2, 8],
                 [1, 6],
                 [7, 12]
                ]
Output: 2

Explanation:
One way to shoot two arrows is to shoot one arrow at x = 6 (through the balloons [1,6] and [2,8]), 
and another arrow at x = 12 (through the balloons [7,12] and [10,16]).

Example 2:

Input: points = [
                 [1, 2],
                 [3, 4],
                 [5, 6],
                 [7, 8]
                ]
Output: 4

Explanation:
Each balloon requires one arrow, as none overlap.

Example 3:

Input: points = [
                 [1, 2],
                 [2, 3],
                 [3, 4],
                 [4, 5]
                ]
Output: 2

Explanation:
One arrow can burst the first three balloons. Another arrow is required to burst the last balloon.

Different Approaches

1️⃣ Greedy Algorithm (Sorting by the Start of the Interval)

In this approach, we sort the balloons (or intervals) by their starting point and then use a greedy strategy to burst as many overlapping balloons as possible using the minimum number of arrows.

Intuition:

The basic idea is to sort the intervals by their start point. Then, we iterate over the sorted intervals and track the minimum end of the overlapping balloons. As long as the next balloon starts before the end of the current range, we can use the same arrow. Once a balloon does not overlap, we know that we need a new arrow.

Steps:

1. Sort the balloons by their start position. This helps us process them from left to right.
2. Initialize an arrow count (arrows = 1) because we need at least one arrow.
3. Keep track of the end of the first balloon (end = points[0][1]).
4. For each subsequent balloon:
   • If it overlaps with the current interval (i.e., points[i][0] <= end), update the end to be the minimum of the current end and the end of the current balloon (this reduces the range where the arrow will burst all overlapping balloons).
   • If it doesn't overlap (i.e., points[i][0] > end), increment the arrow count and update the end to the end of the current balloon (since we need a new arrow).
5. Return the total number of arrows.

Dry Run:

Initialization:

Point {start_x, end_x}

Input: points = [
                 [10, 16],
                 [2, 8],
                 [1, 6],
                 [7, 12]
                ]

Step 1: Sort the Balloons by Start Position:

points = [
          [1, 6],
          [2, 8],
          [7, 12],
          [10, 16]
         ]

Step 2: Initialize the Arrow Count and Track the End:

• Start with the first balloon:
  • We need at least 1 arrow.
  • Set the end = 6 (end of the first balloon [1, 6]).

Step 3: Traverse the Sorted Balloons (from second balloon to last balloon):

• Balloon 2 ([2, 8]):
  • Since the start of the second balloon (2) is less than or equal to the end (6 the end of the first balloon), it overlaps with the first balloon.
  • Update end = min(6, 8) = 6 (we can still burst both balloons with one arrow).
• Balloon 3 ([7, 12]):
  • The start of the third balloon (7) is greater than the current end (6), so it doesn't overlap with the current interval.
  • We need to shoot another arrow.
  • Increment arrows = 2.
  • Set end = 12 (the end of the third balloon).
• Balloon 4 ([10, 16]):
  • The start of the fourth balloon (10) is less than or equal to the current end (12), so it overlaps with the third balloon.
  • Update end = min(12, 16) = 12 (We can burst both balloons with the same arrow).

Final Step: Return the Result:

• We have used 2 arrows to burst all the balloons.
• So, the result is 2.

Code:

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;  // If there are no balloons, no arrows are needed
        
        // Sort the balloons by the start position of the intervals
        sort(points.begin(), points.end());

        int arrows = 1;  // We need at least one arrow to burst the first balloon
        int end = points[0][1];  // Track the end of the first balloon

        // Traverse the balloons from the second one onwards
        for (int i = 1; i < points.size(); i++) {
            // If the start of the current balloon is within the current interval
            if (points[i][0] <= end) {
                // Update the end of the overlapping interval to the minimum end
                end = min(end, points[i][1]);
            } else {
                // If no overlap, shoot a new arrow and update the end to the new balloon's end
                arrows++;
                end = points[i][1];
            }
        }

        return arrows;
    }
};

Complexity Analysis:

• Time Complexity:
  • Sorting the intervals takes O(n log n), where n is the number of balloons.
  • Iterating through the sorted intervals takes O(n).
  • Thus, the overall time complexity is O(n log n).
• Space Complexity:
  • The space complexity is O(1).

2️⃣ Greedy Algorithm (Sorting by the End of the Interval)

In this approach, we sort the balloons (or intervals) by their ending point and use a greedy strategy to burst the maximum number of overlapping balloons with the fewest arrows.

Intuition:

The idea is that if you sort the intervals by their end, then the best place to shoot an arrow is at the end of the first interval. This ensures that the arrow will burst as many subsequent overlapping balloons as possible. Once a balloon no longer overlaps with the current arrow position, we know we need a new arrow, and we repeat the process for the next balloon.

Steps:

1. Sort the balloons by their end position. This way, we can prioritize balloons that end earlier.
2. Initialize the number of arrows (arrows = 1) and set the position of the first arrow to the end of the first balloon (arrowPos = points[0][1]).
3. Iterate through the sorted balloons:
   • If the current balloon's start position is after the current arrow position (i.e., points[i][0] > arrowPos), it means this balloon is out of range of the current arrow, so we shoot a new arrow.
   • Update the arrow position to the end of the current balloon.
4. Return the total number of arrows.

Dry Run:

Initialization:

Point {start_x, end_x}

Input: points = [
                 [10, 16],
                 [2, 8],
                 [1, 6],
                 [7, 12]
                ]

Step 1: Sort the Balloons by End Position:

After sorting based on the end points, we get:

points = [
          [1, 6],
          [2, 8],
          [7, 12],
          [10, 16]
         ]

Step 2: Initialize the Arrow Count and Track the First Arrow Position:

• Start with the first balloon:
  • We need at least 1 arrow.
  • Set the arrowPos = 6 (end of the first balloon [1, 6]).

Step 3: Traverse the Sorted Balloons:

• Balloon 2 ([2, 8]):
  • The start of the second balloon (2) is less than or equal to the current arrowPos (6), meaning it overlaps with the first balloon.
  • We can burst this balloon with the same arrow.
• Balloon 3 ([7, 12]):
  • The start of the third balloon (7) is greater than the current arrowPos (6), so it doesn't overlap with the first balloon.
  • We need to shoot a new arrow.
  • Increment arrows = 2.
  • Set arrowPos = 12 (the end of the third balloon).
• Balloon 4 ([10, 16]):
  • The start of the fourth balloon (10) is less than or equal to the current arrowPos (12), meaning it overlaps with the third balloon.
  • We can burst this balloon with the same arrow.

Final Step: Return the Result:

• We have used 2 arrows to burst all the balloons.
• So, the result is 2.

Code:

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;  // If no balloons, no arrows needed
        
        // Sort balloons by their end position
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });

        int arrows = 1;  // We need at least one arrow for the first balloon
        int arrowPos = points[0][1];  // Position the first arrow at the end of the first balloon

        // Traverse through the sorted balloons
        for (int i = 1; i < points.size(); i++) {
            // If the current balloon's start is after the current arrow position, we need a new arrow
            if (points[i][0] > arrowPos) {
                arrows++;  // Shoot a new arrow
                arrowPos = points[i][1];  // Update arrow position to the end of the current balloon
            }
        }

        return arrows;
    }
};

Complexity Analysis:

• Time Complexity:
  • Sorting the intervals takes O(n log n), where n is the number of balloons.
  • Iterating through the sorted intervals takes O(n).
  • Thus, the overall time complexity is O(n log n).
• Space Complexity:
  • The space complexity is O(1), ignoring the space used by the input.