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


  • 1
    J

    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;
        }
    

Log in to reply
 

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