C++ easy understood solution (sort)


  • 14
    W

    First, we sort balloons by increasing points.end (if ends are the same, then by increasing of points.start). Every time arrow shot points.end, say, points[i].second. If next balloon.start <= points[i].second, it is also shot, thus we continue.

        int findMinArrowShots(vector<pair<int, int>>& points) {
            int count = 0, arrow = INT_MIN;
            sort(points.begin(), points.end(), mysort);
            for(int i = 0; i<points.size(); i++){
                if(arrow!=INT_MIN && points[i].first<=arrow){continue;} //former arrow shot points[i] 
                arrow = points[i].second; // new arrow shot the end of points[i]
                count++;
            }
            return count;
        }
        static bool mysort(pair<int, int>& a, pair<int, int>& b){
            return a.second==b.second?a.first<b.first:a.second<b.second;
        }
    

  • 0
    4

    Can you tell me why you sort the end of the point?


  • 1
    P

    Thanks for your answer, it works. but I think that the mysort() function shall be more simple. My mysort() is:

    static bool mysort(pair<int, int>& a, pair<int, int>& b) {
    return a.second<b.second;
    }

    My solution is accepted, too.


  • 1
    W

    @409396232 Since I will always choose the end point to shoot (in this way, we will get minimum shoots). If you sort by start-point, for example, [1,10],[2,3] after shooting 10, we will move on to 11, then we will miss the [2,3].


  • 0
    W

    @paladin oh thank you! I am not that familiar with sort.


  • 0
    Z

    Nit: there is no need to come up with your own comparator for pair<int, int>. C++ already handles it for you.


  • 0
    W

    @Zhuzeng Thanks!


  • 0
    J

    Guys (and girls), this is the same question as interval scheduling.


  • 0
    S

    Thanks for your solution, I think we only need to sort the points by the end of each one.
    It is not necessary to sort based on the start of point when the end are the same.

    public class Solution {
        public int findMinArrowShots(int[][] points) {
            Arrays.sort(points, (int[] pt1, int[]pt2) -> pt1[1] - pt2[1]);
            if (points.length < 1)
                return 0;
            int endOfPreviousPoint = Integer.MIN_VALUE;
            int count =0;
            for (int i =0; i < points.length; i++){
                int st = points[i][0];
                int end = points[i][1];
                if (endOfPreviousPoint != Integer.MIN_VALUE && endOfPreviousPoint >= st) continue;
                count ++;
                endOfPreviousPoint = end;
            }
            return count;
        }
    }

  • 0
    F

    Reverse thinking is more concise.

    1. sort pairs based on the first element of a pair.
    2. start from the last pair. Each time we choose point.first() as shot place, remove overlap pairs from the array. Repeat it until we exhaust the array.
     -----------------
       -----
       ↑      -----
     2nd shot   ---------
                ↑
             1st shot
    
    class Solution {
    public:
        int findMinArrowShots(vector<pair<int, int>>& points) {
           sort(points.begin(), points.end());
           int shots = 0, n = points.size();
           int i = n - 1;
           while (i >= 0) {
               shots++;
               int shot = points[i].first;
               while (i >= 1 && points[i - 1].second >= shot) i--;
               i--;
           }
           return shots;
        }
    };
    

  • 0
    J

    @fangrui006 Nice reverse thinking way! THX


  • 0
    T
    This post is deleted!

  • 0
    T

    @westwatermelon indeed,sort by start-point works as well, for your example [1,10],[2,3] ,we just need shoot 3 instead of 10. So when we update the end-point when current point's end is smaller than the previous farthest possible end.


Log in to reply
 

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