# Simple 4 lines O(NlogN) C++ implementation with step by step thought process.

• Thought process:

INTUITION: For each interval, there must be at least 1 arrow, the question is which location is the best place to fire arrow.

CLAIM: Foe an interval [a,b], if b is the earliest end point among the intervals, the best location to shoot is at exactly the endpoint b.

REASON: If we shoot at any location x, where x < b, we can always burst the the same or more balloons if we shoot at b. This is because if the arrow at x burst balloon [c,d], then arrow at b also burst it since c<= x < b <= d.

IMPLEMENTATION:
Step 1: Sort intervals according to endpoints.
Step 2: Keep track of most recent arrow location.
Step 3: Fire new arrow if the most recent arrow is out of range.

``````    int findMinArrowShots(vector<pair<int, int>>& points) {
int prevArrow, arrowCount = 0;
sort( points.begin(), points.end(), [](pair<int,int> a, pair<int,int> b){return a.second<b.second;});
for( auto pt: points ) if( arrowCount == 0||pt.first > prevArrow ){ arrowCount++; prevArrow = pt.second;}
return arrowCount;
}
``````

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