# Minimum Number of Arrows to Burst Balloons

## [Minimum Number of Arrows to Burst Balloons](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons)

There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with `xstart` and `xend` bursts by an arrow shot at `x` if `xstart ≤ x ≤ xend`. There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely.

Given an array `points` where `points[i] = [xstart, xend]`, 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: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
```

**Example 2:**

```

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
```

**Example 3:**

```

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
```

**Example 4:**

```

Input: points = [[1,2]]
Output: 1
```

**Example 5:**

```

Input: points = [[2,3],[2,3]]
Output: 1
```

**Constraints:**

* `0 <= points.length <= 104`
* `points[i].length == 2`
* `-231 <= xstart < xend <= 231 - 1`

## Solutions

### 🧠 Cpp

```cpp
class Solution
{
    enum {START, END};

public:
    //O(n log n) solution, because of sorting
    //sort intervals by END, (wider first if ENDs are the same)
    //and check for overlaps with current->at(END) < next_iter->at(START)
    int findMinArrowShots(vector<vector<int>>& points)
    {
        //sort by END value, if equal: put wider intervals first
        std::sort(begin(points), end(points),
                  [](auto a, auto b)
                  {
                      return a[END] == b[END] ? 
                      a[START] > b[START] :
                      a[END] < b[END];
                  });

        int arrow_num = 0;
        for(auto current = begin(points); current != end(points);)
        {
            //count all intervals that overlaps with current
            //still O(n) because we moving forward in vector
            for(auto next_iter = next(current); ; ++next_iter)
            {
                if(next_iter == end(points) || 
                   current->at(END) < next_iter->at(START))
                {
                    arrow_num++;
                    current = next_iter;
                    break;
                }
                //else there is overlap with current
            }
        }

        return arrow_num;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/medium/minimum-number-of-arrows-to-burst-balloons.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.