# 【leetcode】452. Minimum Number of Arrows to Burst Balloons(【leetcode】452. Minimum Number of Arrows to Burst Balloons)-其他

## 【leetcode】452. Minimum Number of Arrows to Burst Balloons(【leetcode】452. Minimum Number of Arrows to Burst Balloons)

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

``points``
``points[i] = [xstart, xend]``
``xstart``
``xend``

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with  and  is burst by an arrow shot at  if . 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.

``xstart``
``xend``
``x``
``xstart <= x <= xend``

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

``points``

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.``````
``````bool cmp(vector<int>&a,vector<int>&b){return a[1]<b[1];}
class Solution {
public:

int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),cmp);
int res=1,end=points[0][1];
for(int i=1;i<points.size();++i){
if(points[i][0]<=end) {
end=min(end,points[i][1]);
}
else{
res++;
end=points[i][1];
}
}
return res;
}
};``````
————————

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

``points``
``points[i] = [xstart, xend]``
``xstart``
``xend``

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with  and  is burst by an arrow shot at  if . 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.

``xstart``
``xend``
``x``
``xstart <= x <= xend``

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

``points``

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.``````
``````bool cmp(vector<int>&a,vector<int>&b){return a[1]<b[1];}
class Solution {
public:

int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),cmp);
int res=1,end=points[0][1];
for(int i=1;i<points.size();++i){
if(points[i][0]<=end) {
end=min(end,points[i][1]);
}
else{
res++;
end=points[i][1];
}
}
return res;
}
};``````