Share my explained Greedy solution as the highest voted java solution right now is not ideal


  • 44
    J

    No offense but the currently highest voted java solution is not ideal, the sorting can be adjusted so that there's no need to check again in the for loop.

    Idea:
    We know that eventually we have to shoot down every balloon, so for each ballon there must be an arrow whose position is between balloon[0] and balloon[1]. Given that, we can sort the array of balloons by their ending position. Then we make sure that while we take care of each balloon from the beginning, we can shoot as many following balloons as possible.

    So what position should we pick? We should shoot as right as possible, because all balloons' end position is to the right of the current one. Therefore the position should be currentBalloon[1], because we still need to shoot down the current one.

    This is exactly what I do in the for loop: check how many balloons I can shoot down with one shot aiming at the ending position of the current balloon. Then I skip all these balloons and start again from the next one (or the leftmost remaining one) that needs another arrow.

    Example:

    balloons = [[7,10], [1,5], [3,6], [2,4], [1,4]]
    

    After sorting, it becomes:

    balloons = [[2,4], [1,4], [1,5], [3,6], [7,10]]
    

    So first of all, we shoot at position 4, we go through the array and see that all first 4 balloons can be taken care of by this single shot. Then we need another shot for one last balloon. So the result should be 2.

    Code:

    public int findMinArrowShots(int[][] points) {
            if (points.length == 0) {
                return 0;
            }
            Arrays.sort(points, (a, b) -> a[1] - b[1]);
            int arrowPos = points[0][1];
            int arrowCnt = 1;
            for (int i = 1; i < points.length; i++) {
                if (arrowPos >= points[i][0]) {
                    continue;
                }
                arrowCnt++;
                arrowPos = points[i][1];
            }
            return arrowCnt;
        }
    

  • 2

    Almost the same with 435. Non-overlapping Intervals
    See also: https://discuss.leetcode.com/topic/65594/java-least-is-most/10

    public int findMinArrowShots(int[][] points) {
            int count = 0;
            long end = Long.MIN_VALUE;
            Arrays.sort(points, (a, b) -> (a[1]-b[1]));
    
            for(int[] p: points){
                if(p[0] > end){
                    end = p[1];
                    count++;
                }
            }
    
            return count;
        }
    

  • 0
    R

    How to explain the test case: [[1,4],[1,8],[5,6],[7,9]]? its result should be 2, but leetcode's answer is 3.


  • 0

    @redspace How can you do that in 2?


  • 0
    R

    @snapfinger
    Sorry, I need to correct one number: [[1,4],[2,8],[5,6],[7,9]]
    The first shot is [1,4] at 1, then the second shot is at 8 to burst the rest three


  • 0

    @redspace Are you sure you can burst the rest of the three by shooting 8?


  • 0
    R

    @snapfinger En. Not 8, but 6.


  • 0
    V

    @redspace If you shoot at 6, [7,9] doesn't get burst, right?


  • 0
    N

    My thoughts are exactly same.
    Code in Cpp.

    class Solution {
    public:
        class Compare 
        {
        public:
            bool operator() (const std::pair<int, int> &one, const std::pair<int, int> &two)
            {
                return one.second < two.second;
            }
        } compare;
        int findMinArrowShots(vector<pair<int, int>>& points) {
            int n = points.size();
            if (n < 2)
                return n;
            std::sort(points.begin(), points.end(), compare);
            int count = 1;
            int end = points[0].second;
            for (int i = 1; i < n; i++)
            {
                if (points[i].first <= end)
                    continue;
                count++;
                end = points[i].second;
            }
            return count;
        }
    };
    

  • 0
    W

    Thanks for your solution, but I'm confused that why [[1,10], [1,5], [5,6], [2,4], [1,4]] takes two shots but not one, because if shoot among [1, 10], every balloon would be covered, while according to your sorting, it would become [[2, 4], [1, 4], [1, 5], [5, 6], [1, 10]], the second shot is created by [5, 6].
    Thanks.


  • 0
    R

    @wei166 one shot can be only on one index,which means you need to choose one index among 1 to 10.


  • 0
    W

    @roger367 yes, so what if I choose to shoot 8, which is between [1,10], doesn't it burst all balloons? so the answer is 1 instead of 2?


Log in to reply
 

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