Intervals - Minimum Number of Arrows to Burst Balloons

Balloons are represented as intervals [xstart, xend]. An arrow shot at x bursts all balloons containing x. Find the minimum number of arrows to burst all balloons.

Input: [[10,16],[2,8],[1,6],[7,12]] → Output: 2

Input: [[1,2],[3,4],[5,6],[7,8]] → Output: 4

Greedy: sort by end. Shoot the arrow at the end of the first balloon. All overlapping balloons also burst. Move to the next unbursted balloon.

Sort by end time.
Shoot arrow at intervals[0][1]. Count = 1.
For each next interval: if its start > current arrow position, shoot a new arrow at its end, count++.

import java.util.*; class Solution { public int findMinArrowShots(int[][] points) { Arrays.sort(points, (a,b) -> Integer.compare(a[1],b[1])); int arrows = 1, arrowAt = points[0][1]; for (int[] p : points) { if (p[0] > arrowAt) { arrows++; arrowAt = p[1]; } } return arrows; } }

Time Complexity: O(N log N)
Space Complexity: O(1)