Find Minimum Number of Arrows Needed to Burst all Balloons

Algorithm -

Step 1. Create a function"minRequiredArrows()" to find the minimum number of arrows needed to burst all balloons, which takes a 2-dimensional vector storing the starting and ending x-coordinate of balloons as input.

Step 2. Inside the function "minRequiredArrows()," first sort the ‘balloons’ vector in the increasing order of the ending x-coordinates of balloons.

Step 3. Then initialize two variables ‘numArrows’ and ‘arrowPosn’ to store the number of arrows needed and the current position of the arrow respectively. 

Step 4. Initialize ‘numArrows = 1’ as at least one arrow will be required and ‘arrowPosn = ending x-coordinate of first balloon’ as we have to burst the first balloon and take the best coordinate greedily at each step.

Step 5. Now iterate through all the remaining balloons and check whether the current balloon can be burst with the current arrow position. If it can burst then move to the next balloon else, increase the number of arrows, and change the position of the arrow greedily with the ending x-coordinate of the current balloon.

Step 6. Finally, return the ‘numArrows’, which is the minimum number of arrows needed to burst all balloons

C++ code:

// C++ code to find the minimum number of arrows needed to burst all balloons
#include <bits/stdc++.h>
using namespace std;


bool comp(vector<int> a, vector<int> b)
{
	return b[1] > a[1];
}


// Function to find the minimum number of arrows needed to burst all balloons
int minRequiredArrows(vector<vector<int>> balloons)
{

	// Sort the vector of balloons in the increasing order of their end points
	sort(balloons.begin(), balloons.end(), comp);


	// Initialize number of arrows with 1
	int numArrows = 1;

	// Initialize the arrow position with the ending x-coordinate of first balloon
	int arrowPosn = balloons[0][1];


	// Iterate through all the balloons and burst them 
	for (int i = 1; i < balloons.size(); i++)
	{

	  /*
		If current position of arrow is greater than the starting x-coordinate of the balloon,
		then the same arrow will burst this balloon, so do nothing and move to the next balloon.
		Else increase the number of arrows and change the position of arrow to the ending 
		x-coordinate of the balloon
      */
		if (arrowPosn >= balloons[i][0])
		{
			continue;
		}
		else
		{
			arrowPosn = balloons[i][1];
			numArrows++;
		}
	}


	// Return the total number of arrows needed to burst all the balloons
	return numArrows;
}


// Main Function
int main()
{

	// Number of balloons
	int N = 5;
    	
	// Declare a vector of vector to store the starting and ending x-coordinate of the balloons
	vector<vector<int>> balloons;
    	
	// Push the starting and ending x-coordinate of the balloons into the vector
	balloons.push_back({1,6});
	balloons.push_back({11,17});
	balloons.push_back({16,21});
	balloons.push_back({3,8});
	balloons.push_back({7,19});
     	
	// Call the function to find the minimum number of arrows needed to burst all balloons
	int minArrows = minRequiredArrows(balloons);

	cout<<"The minimum number of arrows needed to burst all balloons are: "<<minArrows<<endl;

	return 0;
}

Output:
The minimum number of arrows needed to burst all balloons are: 2

Algorithm Complexity: 

Time Complexity: O(N log(N))

In the function "minRequiredArrows()" to find the minimum number of arrows needed to burst all balloons, first, the vector is sorted which takes O(N log(N)) time and then a ‘for loop’ is used to iterate through the vector which takes O(N) time. So, the overall time complexity is O(N log(N)), where 'N' is the total number of balloons.

Space Complexity: O(1) 

In the function "minRequiredArrows()" to find the minimum number of arrows needed to burst all balloons, we have used constant space, So, the space complexity is O(1).

FAQs

1. What is a Greedy Algorithm? 
   Greedy algorithm is a technique to solve the problem by breaking into smaller steps and choosing the best possible solution at each step.
    

2. In the above approach to solve the problem, why we are changing the arrow position to the ending x coordinate of the balloon on getting a balloon that can’t be burst with the previous array?
We are greedily taking the best possible position for the arrow at each step. As we are moving from left to right, so, we are taking the rightmost position of the arrow that can burst the current balloon and can be helpful in bursting the next balloons also as we have to minimize the number of arrows needed.

 Also Read - Strong number in c

Key takeaways-

This article discussed the problem "Find the minimum number of arrows needed to burst all balloons, " the solution approach to this problem,  its C++ implementation, and its time and space complexity.

If you want to solve similar problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.