# 5-line C++ O(NlogN) concise solution with clean explanation

• Key observation: any balloons with common range could be burst using a single arrow, so the problem is simply to ask how many disjoint common ranges formed by given balloons?

Sort all balloons { Bi=1:N } by left edge x-coordinates. Note that if balloon subset { Bi } has a non-empty common range, clearly, we have

• common range [L, R] = [maxi Bi.left, mini Bi.right].

The position of current balloon Bcur v.s. last common range is either

• intersecting, i.e., Bcur.left ≤ R, which means no addition arrow needed and we update to shrink the common range,
• or disjoint, which means we discard the last common range since current balloon becomes the new common range, and we need a new arrow to burst it.
``````    int findMinArrowShots(vector<pair<int, int>>& points) {
sort(points.begin(), points.end(), [](pair<int, int>& a, pair<int, int>& b){return a.first<b.first;});
int res = 1; pair<int, int> common(INT_MIN, INT_MAX);
for (auto& p:points)
common = (p.first > common.second)? (++res,p) : make_pair(p.first, min(common.second, p.second));
return points.empty()? 0 : res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.