# LeetCode 452: Minimum Number of Arrows to Burst Balloons

## Problem Restatement

We are given a list of balloons.

Each balloon is represented by an interval:

```python
[xstart, xend]
```

This means the balloon covers every horizontal position from `xstart` to `xend`, inclusive.

An arrow is shot vertically upward from some x-coordinate `x`.

The arrow bursts a balloon if:

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

One arrow can burst many balloons if their intervals all contain the same x-coordinate.

We need to return the minimum number of arrows needed to burst every balloon.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `points`, a list of intervals |
| Interval | `points[i] = [xstart, xend]` |
| Output | Minimum number of arrows |
| Rule | One arrow at `x` bursts every interval containing `x` |

Function shape:

```python
def findMinArrowShots(points: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

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

Sort by ending coordinate:

```python
[1,6], [2,8], [7,12], [10,16]
```

Shoot one arrow at `x = 6`.

It bursts:

```python
[1,6]
[2,8]
```

The next balloon `[7,12]` starts after `6`, so the arrow at `6` cannot hit it.

Shoot another arrow at `x = 12`.

It bursts:

```python
[7,12]
[10,16]
```

Answer:

```python
2
```

Example 2:

```python
points = [[1,2],[3,4],[5,6],[7,8]]
```

No intervals overlap.

Each balloon needs its own arrow.

Answer:

```python
4
```

Example 3:

```python
points = [[1,2],[2,3],[3,4],[4,5]]
```

The intervals are inclusive.

An arrow at `x = 2` bursts:

```python
[1,2]
[2,3]
```

An arrow at `x = 4` bursts:

```python
[3,4]
[4,5]
```

Answer:

```python
2
```

## First Thought: Brute Force

One direct idea is to try many possible arrow positions.

For each balloon, we could try shooting at its start or end coordinate, then remove every balloon hit by that arrow.

But this approach is awkward.

The coordinates can be very large:

```python
-2^31 <= xstart < xend <= 2^31 - 1
```

So we cannot scan every x-coordinate.

Also, choosing an arrow position greedily without sorting can make poor choices.

We need a rule that always gives a safe arrow position.

## Problem With Brute Force

The main problem is that we are choosing points to cover intervals.

Trying all possible choices grows too quickly.

If there are `n` balloons, a naive search over possible groups of balloons can become exponential.

Even trying every endpoint against every interval costs at least:

```python
O(n^2)
```

With up to `10^5` balloons, this is too slow.

We need an `O(n log n)` solution.

The sorting step is acceptable. Repeatedly comparing every interval with every other interval is not.

## Key Insight

This is an interval covering problem.

If we sort balloons by their ending coordinate, the best place to shoot the first arrow is at the end of the earliest-ending balloon.

Suppose the earliest-ending balloon is:

```python
[start, end]
```

Any arrow that bursts this balloon must be shot somewhere between `start` and `end`.

Choosing `x = end` is best because it is as far right as possible while still hitting this balloon.

That gives the arrow the greatest chance to also hit future balloons.

So the greedy rule is:

1. Sort balloons by `xend`.
2. Shoot an arrow at the end of the first uncovered balloon.
3. Skip every balloon that this arrow hits.
4. Repeat.

## Algorithm

Sort `points` by the interval end:

```python
points.sort(key=lambda p: p[1])
```

Set:

```python
arrows = 0
arrow_x = -infinity
```

Then scan the sorted intervals.

For each balloon `[start, end]`:

If the current arrow position already hits it:

```python
start <= arrow_x <= end
```

then we do nothing.

Because we sorted by end, and `arrow_x` was chosen as an earlier end, it is enough to check:

```python
start <= arrow_x
```

If:

```python
start > arrow_x
```

then the current balloon is not covered.

We need a new arrow.

Place it at:

```python
arrow_x = end
```

and increment `arrows`.

## Correctness

After sorting by ending coordinate, consider the first balloon that has not yet been burst.

Let that balloon be:

```python
[start, end]
```

Any valid solution must use at least one arrow to burst this balloon.

That arrow must be placed in the interval `[start, end]`.

Placing the arrow at `end` is safe because it still bursts this balloon. It is also the rightmost possible valid position for this balloon, so it can only help with later balloons whose starts may be larger.

Once we place an arrow at `end`, every later balloon with:

```python
start <= end
```

is also burst by this arrow.

Every later balloon with:

```python
start > end
```

cannot be burst by this arrow or by any arrow that was required to hit the earlier balloon at or before `end`.

So a new arrow is necessary.

The algorithm adds a new arrow exactly when the current balloon cannot be hit by the previous arrow. Therefore, it never uses an unnecessary arrow, and it never leaves a balloon unburst.

Thus, the algorithm returns the minimum number of arrows.

## Complexity

Let `n` be the number of balloons.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting dominates the runtime |
| Space | `O(1)` or `O(n)` | The scan uses constant extra space, but sorting may use extra space depending on implementation |

In Python, sorting uses extra memory internally, so the practical space cost can be `O(n)`.

## Implementation

```python
class Solution:
    def findMinArrowShots(self, points: list[list[int]]) -> int:
        points.sort(key=lambda p: p[1])

        arrows = 0
        arrow_x = float("-inf")

        for start, end in points:
            if start > arrow_x:
                arrows += 1
                arrow_x = end

        return arrows
```

## Code Explanation

We sort intervals by their ending coordinate:

```python
points.sort(key=lambda p: p[1])
```

This lets us always handle the balloon that finishes earliest.

Then we initialize:

```python
arrows = 0
arrow_x = float("-inf")
```

At the beginning, no arrow has been shot yet.

So `arrow_x` is set to negative infinity to ensure the first balloon needs a new arrow.

Now we scan each balloon:

```python
for start, end in points:
```

If the current balloon starts after the last arrow position:

```python
if start > arrow_x:
```

then the previous arrow cannot burst this balloon.

So we shoot a new arrow:

```python
arrows += 1
arrow_x = end
```

We place the arrow at the current balloon's end because this is the rightmost position that still bursts it.

Finally, return the number of arrows:

```python
return arrows
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findMinArrowShots([[10,16],[2,8],[1,6],[7,12]]) == 2
    assert s.findMinArrowShots([[1,2],[3,4],[5,6],[7,8]]) == 4
    assert s.findMinArrowShots([[1,2],[2,3],[3,4],[4,5]]) == 2
    assert s.findMinArrowShots([[1,2]]) == 1
    assert s.findMinArrowShots([[1,10],[2,3],[4,5],[6,7],[8,9]]) == 4
    assert s.findMinArrowShots([[-2147483648,2147483647]]) == 1
    assert s.findMinArrowShots([[1,100],[2,99],[3,98],[4,97]]) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[[10,16],[2,8],[1,6],[7,12]]` | Standard overlapping groups |
| `[[1,2],[3,4],[5,6],[7,8]]` | No overlap |
| `[[1,2],[2,3],[3,4],[4,5]]` | Inclusive endpoints |
| `[[1,2]]` | Single balloon |
| `[[1,10],[2,3],[4,5],[6,7],[8,9]]` | One large interval with many disjoint smaller ones |
| `[[-2147483648,2147483647]]` | Large coordinate range |
| `[[1,100],[2,99],[3,98],[4,97]]` | Fully nested intervals |