In this guide, we will explore the process of determining the minimum quantity of arrows required to pop all balloons using C++.
Problem Statement:
Given an array of size N, with each element points[i] representing a balloon that spans the interval between pointsi and pointsi along the X-axis, regardless of their Y-coordinates. Ensuring the bursting of every balloon is crucial. To achieve this, an arrow can be launched from the point (x, 0) to burst a balloon if the condition pointsi <= x \= pointsi is met. Upon hitting a balloon, the arrow moves vertically upwards. The objective here is to determine the minimum number of arrows needed to pop all balloons.
We can use the following procedures to determine the minimum number of arrows required to burst every balloon:
- Using their terminal locations as a starting point, sort the balloons.
- Set up a variable to record the number of arrows required, and another to record the balloon's current end coordinate.
- Check all the sorted balloons one by one. Update the end coordinate to the current balloon's end coordinate and increase the arrow count if the current balloon's start coordinate is larger than the end coordinate that was previously stored.
- If the start coordinate of the current balloon lies within the stored end coordinate, update the stored end coordinate to the smaller value between the saved end coordinate and the current balloon's end coordinate.
- Balloons: {{10, 16}, {2, 8}, {1, 6}, {7, 12}} Sorting by end coordinates: {{1, 6}, {2, 8}, {7, 12}, {10, 16}} Arrows needed to burst all balloons: 2
- Balloons: {{1, 2}, {3, 4}, {5, 6}, {7, 8}} Sort based on the end coordinates: {{1, 2}, {3, 4}, {5, 6}, {7, 8}} Arrows needed to burst all balloons: 4
- Balloons: {{1, 2}, {2, 3}, {3, 4}, {4, 5}} Sorting by end coordinates: {{1, 2}, {2, 3}, {3, 4}, {4, 5}} Arrows needed to burst all balloons : 2
Examples:
Pseudocode:
function findMinArrowShots(balloons):
if balloons are empty:
return 0
Sort balloons by end coordinate
arrows = 1
end = balloons[0].end
for i from 1 to length of balloons:
if balloons[i].start > end:
arrows++
end=balloons[i].end
else:
end = min(end, balloons[i].end)
return arrows
Example 1:
Examine a sample code snippet to determine the minimum quantity of arrows needed to burst all the balloons in C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMinArrowShots(vector<vector<int>>& point) {
if (point.empty()) return 0;
sort(point.begin(), point.end(), [](const vector<int>& x, const vector<int>& y) {
return x[1] < y[1];
});
int arrows = 1;
int end = point[0][1];
for (int i = 1; i < point.size(); i++) {
if (point[i][0] > end) {
arrows++;
end = point[i][1];
} else {
end = min(end, point[i][1]);
}
}
return arrows;
}
int main() {
vector<vector<int>> balloons = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
cout << "Minimum number of arrows needed: " << findMinArrowShots(balloons) << endl;
return 0;
}
Output:
Example 2:
Let's consider another instance to determine the minimum quantity of arrows required to pop all balloons in C++.
#include <bits/stdc++.h>
using namespace std;
bool cmp(vector<int> a, vector<int> b)
{
return b[1] > a[1];
}
int minArrows(vector<vector<int>> points)
{
// To sort our array according
// to end position of balloons
sort(points.begin(), points.end(), cmp);
// Initialize end variable with
//The end of the first balloon
int end = points[0][1];
// Initialize arrow with 1
int arrow = 1;
// Iterate through the entire
// arrow of points
for (int i=1;i<points.size();++i)
{
// If the start of ith balloon
// <= end than do nothing
if (points[i][0] <= end)
{
continue;
}
else
{
// Update the new end
end=points[i][1];
arrow++;
}
}
return arrow;
}
// Driver code
int main()
{
vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
cout << (minArrows(points));
return 0;
}
Output:
Example 3:
Let's explore another instance where we determine the minimum number of arrows required to pop all balloons in C++.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Balloon {
int start;
int end;
Balloon(int s, int e) : start(s), end(e) {}
};
int findMinArrowShots(vector<Balloon>& balloons) {
if (balloons.empty()) return 0;
sort(balloons.begin(), balloons.end(), [](const Balloon& x, const Balloon& y) {
return x.end < y.end;
});
int arrs = 1;
int end = balloons[0].end;
for (int i = 1; i < balloons.size(); i++) {
if (balloons[i].start > end) {
arrs++;
end = balloons[i].end;
} else {
end = min(end, balloons[i].end);
}
}
return arrs;
}
int main() {
vector<Balloon> balloons = {Balloon(10, 16), Balloon(2, 8), Balloon(1, 6), Balloon(7, 12)};
cout << "Minimum number of arrows needed: " << findMinArrowShots(balloons) << endl;
return 0;
}
Output:
