Welcome to Subscribe On Youtube
452. Minimum Number of Arrows to Burst Balloons
Description
There are some spherical balloons taped onto a flat wall that represents the XYplane. The balloons are represented as a 2D integer array points
where points[i] = [x_{start}, x_{end}]
denotes a balloon whose horizontal diameter stretches between x_{start}
and x_{end}
. You do not know the exact ycoordinates of the balloons.
Arrows can be shot up directly vertically (in the positive ydirection) from different points along the xaxis. A balloon with x_{start}
and x_{end}
is burst by an arrow shot at x
if x_{start} <= x <= x_{end}
. 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.
Given the array points
, return the minimum number of arrows that must be shot to burst all balloons.
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.
Example 3:
Input: points = [[1,2],[2,3],[3,4],[4,5]] Output: 2 Explanation: The balloons can be burst by 2 arrows:  Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].  Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].
Constraints:
1 <= points.length <= 10^{5}
points[i].length == 2
2^{31} <= x_{start} < x_{end} <= 2^{31}  1
Solutions

class Solution { public int findMinArrowShots(int[][] points) { Arrays.sort(points, Comparator.comparingInt(a > a[1])); int ans = 0; long last = (1L << 60); for (var p : points) { int a = p[0], b = p[1]; if (a > last) { ++ans; last = b; } } return ans; } }

class Solution { public: int findMinArrowShots(vector<vector<int>>& points) { sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; }); int ans = 0; long long last = (1LL << 60); for (auto& p : points) { int a = p[0], b = p[1]; if (a > last) { ++ans; last = b; } } return ans; } };

class Solution: def findMinArrowShots(self, points: List[List[int]]) > int: ans, last = 0, inf for a, b in sorted(points, key=lambda x: x[1]): if a > last: ans += 1 last = b return ans

func findMinArrowShots(points [][]int) (ans int) { sort.Slice(points, func(i, j int) bool { return points[i][1] < points[j][1] }) last := (1 << 60) for _, p := range points { a, b := p[0], p[1] if a > last { ans++ last = b } } return }

function findMinArrowShots(points: number[][]): number { points.sort((a, b) => a[1]  b[1]); let ans = 0; let last = Infinity; for (const [a, b] of points) { if (last < a) { ans++; last = b; } } return ans; }

public class Solution { public int FindMinArrowShots(int[][] points) { Array.Sort(points, (a, b) => a[1] < b[1] ? 1 : a[1] > b[1] ? 1 : 0); int ans = 0; long last = long.MinValue; foreach (var point in points) { if (point[0] > last) { ++ans; last = point[1]; } } return ans; } }