8.20刷题

发表于 | 分类于 | 0 comments

第一题 452. Minimum Number of Arrows to Burst Balloons

题目描述

二维空间中有一组气球。对于每一个气球，输入其水平直径的起止点坐标。由于是水平的，不需要考虑y坐标，因而用x坐标表示起止点即可。起点总是小于终点。最多10^4个气球。

一支箭从x轴的不同点竖直射出。某气球的起止点坐标为xstart和xend，当xstart ≤ x ≤ xend时，该气球会被射中。射出的弓箭数目没有限制。弓箭可以保持无限移动。计算最少需要多少弓箭可以将所有气球射中。

算法

这题重要的是思路是，只用注意结尾处的位置即可。因为如果结尾进行了排序的话，前面小于结尾的是肯定可以一并扎破的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0 || points[0].length == 0)
            return 0;
        
        Arrays.sort(points, new Comparator<int[]> (){
           @Override
            public int compare(int[] obj1, int[] obj2) {
                return obj1[1] - obj2[1];
            }
        });
        
        int count = 1;
        int endPoint = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= endPoint) {
                continue;
            }
            count++;
            endPoint = points[i][1];
        }
        return count;
    }
}

第二题 435. Non-overlapping Intervals

题目描述

给定一组区间，计算最少需要移除多少区间，才能使剩余区间两两互不相交。

注意：

你可以假设区间的终点总是比起点大
区间[1,2]和[2,3]首尾相接但并不相交

算法

与之前的题目相似，都是找重复部分，思路并没有实质变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals.length == 0)
            return 0;
       Arrays.sort(intervals, (obj1, obj2) -> (obj1.end - obj2.end));
        // Arrays.sort(intervals, new Comparator<Interval>() {
        //     @Override
        //     public int compare(Interval o1, Interval o2) {
        //         return o1.end - o2.end;
        //     }
        // });
        int count = 0;
        int curEnd = intervals[0].end;
        for (int i = 1; i < intervals.length; i++) {
            Interval interval = intervals[i];
            if (interval.start < curEnd) {
                count++;
                continue;
            }
            curEnd = interval.end;
        }
        return count;
    }
}