Minimum Number of Arrows to Burst Balloons

Leave a comment

December 18, 2016 by oneOokay

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xendbursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

题目超级长的一题,但是其实就是Merge Intervals的变体,不同的是,当merge的时候,取交集而不是取并集,范围缩小而不是放大。同时也只需要track overlapping 的end就可以了,start并不需要track。

我自建了一个Pair class用来排序,但是貌似java8里面有lambda可以直接进行排序。

Arrays.sort(points,(a, b) -> a[0] - b[0]);

然后依旧还有那个super easy的java solution在。。。依旧没看。

public class Solution {
    public class Balloon{
        public int x1;
        public int x2;
        public Balloon(int x1, int x2){
            this.x1 = x1;
            this.x2 = x2;
        }
    }
    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0 || points[0].length == 0){
            return 0;
        }
        
        List list = new ArrayList();
        for (int i = 0; i < points.length; i ++){
            list.add(new Balloon(points[i][0], points[i][1]));
        }
        
        Collections.sort(list, new Comparator(){
            public int compare(Balloon b1, Balloon b2){
                if (b1.x1 != b2.x1){
                    return b1.x1 - b2.x1;
                }
                
                if (b1.x2 != b2.x2){
                    return b1.x2 - b2.x2;
                }
                return 0;
            }
        });
        
        //int start = list.get(0).x1;
        int end = list.get(0).x2;
        int arrow = 0;
        for (int i = 0; i < list.size(); i ++){
            Balloon b = list.get(i);
            if (b.x1 <= end){//由这里其实可以看到我们不用track start,只需要
track end 即可
                //start = Math.max(start, b.x1);
                end = Math.min(end, b.x2);
            }else {
                arrow ++;
                //start = b.x1;
                end = b.x2;
            }
        }
        return arrow + 1;//注意这里不能return arrow ++;
        
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: