Crack the Backend

Problem Statement

There are spherical balloons on a 2D plane. points[i] = [x_start, x_end] represents a balloon's horizontal diameter. Arrows are shot vertically (infinite line x = some value); an arrow at x bursts all balloons whose horizontal range contains x. Return the minimum number of arrows needed to burst all balloons.

Key Observations

Sort by end: Sort intervals by x_end. We shoot an arrow at the end of the first interval (or current "cluster"). All intervals that start before or at this x are burst (they contain this x). Then we need a new arrow for the next interval whose start is after this x. So: arrows = 1, end = first interval's end. For each [s, e]: if s > end we need a new arrow, so arrows++, end = e; else the current arrow still bursts this balloon (we might tighten end to min(end, e) but sorting by end means we already process in order — we can just update end = e when we don't need a new arrow to cover overlapping ones). Actually: if s > end, new arrow at e; else we can "extend" the shot to also burst this one (no new arrow). So if s > end then arrows++, end = e.

Approach

High-level: Sort points by end (points[i][1]). arrows = 1, end = points[0][1]. For each [s,e]: if s > end then arrows++, end = e. Return arrows.

Steps: Arrays.sort(points, (a,b)->Integer.compare(a[1],b[1])). int arrows = 1, end = points[0][1]; for each: if (p[0] > end) { arrows++; end = p[1]; } return arrows.

Implementation

Java

public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a,b) -> Integer.compare(a[1], b[1]));
    int arrows = 1, end = points[0][1];

    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > end) { arrows++; end = points[i][1]; }
    }

    return arrows;
}

Test Cases

Example 1

Input

points = [[10,16],[2,8],[1,6],[7,12]]

Expected

2

Explanation

Shoot at 6 and 10.

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.