Description
Given an matrix points, balloons are represented by intervals. An arrow at x bursts balloons where x is in range. Find minimum arrows needed.
Examples
Input:
points = [[10,16],[2,8],[1,6],[7,12]]Output:
2Explanation:
Shoot at x=6 (burst 1,6 and 2,8), x=11 (burst 10,16 and 7,12).
Input:
points = [[1,2]]Output:
1Explanation:
A single balloon at interval [1,2] requires exactly one arrow shot anywhere in that range to burst it.
Input:
points = [[1,4],[2,3],[3,6],[4,5]]Output:
2Explanation:
Two arrows needed. First arrow at x=3 bursts [1,4], [2,3], and [3,6] since 3 is within all three intervals. The remaining balloon [4,5] requires a second arrow at any point in [4,5]. Sorting by end point and greedily shooting at each interval's end minimizes arrows.
Constraints
- •
1 ≤ points.length ≤ 10⁵