Very easy and short C++ solution with explanation [Sort based on start points]


  • 0
    G

    Start iterating the balloons after sorting them based on their start points. The idea is since we must burst the first balloon before moving on, burst as many following balloons as we can with the same arrow (else clause). We need to keep adjusting the current arrow's position to the minimum of all bursting balloons end points to ensure that the arrow will strike all the balloons in the current set. If the next balloon's start point is beyond our current arrow, then start a new arrow (if clause).

    class Solution {
    public:
        int findMinArrowShots(vector<pair<int, int>>& points) {
            sort(points.begin(), points.end());     // sort based on start points
            int arrows = 0;     // num of arrows
            int cur_arrow;      // where we must shoot the current arrow
            for (int i = 0; i < points.size(); i++) {
                if (i == 0 || points[i].first > cur_arrow) {
                    // current arrow cannot burst this balloon, so start a new arrow
                    arrows++;
                    cur_arrow = points[i].second;
                } else {
                    // current arrow can burst this balloon, change the current arrow
                    // *if* this balloon's end point is smaller than the current arrow
                    cur_arrow = min(cur_arrow, points[i].second);
                }
            }
            return arrows;
        }
    };
    

Log in to reply
 

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