Dare2Solve
The problem requires determining the minimum number of vertical arrows needed to burst all the balloons. Each balloon is represented by its horizontal diameter on the x-axis. By shooting an arrow at the end of an interval, we can maximize the number of balloons burst with a single shot, as it ensures covering the largest possible range of overlapping balloons.
Sorting: First, sort the list of intervals by their end coordinates. This allows us to efficiently determine the minimum number of arrows by always aiming at the end of the current interval.
Initialization: Initialize a variable to keep track of the current position of the arrow (current_shot_x
) set to the end of the first interval. Initialize a counter (res
) to count the number of arrows needed.
Iterate Through Intervals: Loop through the sorted list of intervals:
current_shot_x
. If true, it indicates that the current interval is not covered by the current arrow, so we need to shoot a new arrow. Update current_shot_x
to the end of the current interval and increment the counter res
.Return Result: The counter res
now contains the minimum number of arrows needed to burst all balloons.
O(n log n) due to sorting, where n is the number of intervals. The iteration through the intervals takes linear time O(n).
O(1) if we don't count the input array, as no additional space proportional to the input size is used.
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) return 0;
sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int currentShotX = points[0][1];
int res = 1;
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > currentShotX) {
currentShotX = points[i][1];
res++;
}
}
return res;
}
};
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x: x[1])
current_shot_x = points[0][1]
res = 1
for i in range(1, len(points)):
if points[i][0] > current_shot_x:
current_shot_x = points[i][1]
res += 1
return res
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int currentShotX = points[0][1];
int res = 1;
for (int i = 1; i < points.length; i++) {
if (points[i][0] > currentShotX) {
currentShotX = points[i][1];
res++;
}
}
return res;
}
}
var findMinArrowShots = function(points) {
points.sort((a, b) => a[1] - b[1]);
let currentShotX = points[0][1];
let res = 1;
for (let i = 1; i < points.length; i++) {
if (points[i][0] > currentShotX) {
currentShotX = points[i][1];
res++;
}
}
return res;
};