Java, O(nlogn). Sort by end. Short explanation


  • 0
    A

    We need to sort by the ends of the balloons. We can count number of needed arrows greedy. We will try to burst maximum number of balloons by one arrow. If i-th balloon doesn't overlap with previous balloon we need 1 arrow to clear all the previous balloons.

    public class Solution {
        public int findMinArrowShots(int[][] points) {
            if (points.length==0) return 0;
            List<Interval> balloons = getBallons(points);
            Collections.sort(balloons, new Comparator<Interval>() {
                @Override
                public int compare(Interval i1, Interval i2) {
                    return -i1.end.compareTo(i2.end);
                }
            });
            
            int minStart = balloons.get(0).start;
            int arrows = 1;
            for (int i=1; i<balloons.size(); i++) {
                if (balloons.get(i).end<minStart) {
                    arrows++;
                    minStart = balloons.get(i).start;
                } else {
                    minStart = Math.max(balloons.get(i).start, minStart);
                }
                
            }
            return arrows;
        }
        
        private List<Interval> getBallons(int[][] points) {
            List<Interval> balloons = new ArrayList<Interval>();
            for (int i=0; i<points.length; i++) {
                balloons.add(new Interval(points[i][0], points[i][1]));
            }
            return balloons;
        }
        
        
        class Interval {
            Integer start;
            Integer end;
            public Interval(Integer start, Integer end) {
                this.start = start;
                this.end = end;
            }
        }
    }
    

Log in to reply
 

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