452. 用最少数量的箭引爆气球(中等)

Posted on In Views:

1，问题描述

452. 用最少数量的箭引爆气球

难度：中等

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

1
2
3
4
5
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

1
2
3
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

1
2
3
4
5
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -231 <= xstart < xend <= 2^31 - 1

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
package questions;

import java.util.*;

public class _452用最少数量的箭引爆气球 {

    // 官方解法
    public int findMinArrowShots_optimize_gov(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        Arrays.sort(points, new Comparator<int[]>() {
            public int compare(int[] point1, int[] point2) {
                if (point1[1] > point2[1]) {
                    return 1;
                } else if (point1[1] < point2[1]) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        int pos = points[0][1];
        int ans = 1;
        for (int[] balloon : points) {
            if (balloon[0] > pos) {
                pos = balloon[1];
                ++ans;
            }
        }
        return ans;
    }


    // 线段树，需要先排序
    public int findMinArrowShots_optimize(int[][] points) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        for (int i = 0; i < points.length; i++) {
            pq.add(points[i]);
        }// 升序即可

        List<int[]> list = new ArrayList<>();
        while (!pq.isEmpty()) {
            int[] poll = pq.poll();
            boolean merged = false;
            for (int j = 0; j < list.size(); j++) {
                merged = merge(list.get(j), poll);
                if (merged) {
                    break;
                }
            }
            if (!merged) {
                list.add(poll);
            }
        }

        return list.size();
    }


    // 区间树（只能往中间趋近）
    public int findMinArrowShots_fial(int[][] points) {
        List<int[]> list = new ArrayList<>();
        list.add(new int[]{points[0][0], points[0][1]});
        for (int i = 1; i < points.length; i++) {
            boolean merged = false;
            for (int j = 0; j < list.size(); j++) {
                merged = merge(list.get(j), points[i]);
                if (merged) {
                    break;
                }
            }
            if (!merged) {
                list.add(new int[]{points[i][0], points[i][1]});
            }
        }
        return list.size();
    }

    private boolean merge(int[] a, int[] b) {
        if (a[1] < b[0] || a[0] > b[1]) {
            return false;
        }// 不相交
        a[0] = Math.max(a[0], b[0]);
        a[1] = Math.min(a[1], b[1]);
        return true;
    }

    public static void main(String[] args) {
        _452用最少数量的箭引爆气球 q = new _452用最少数量的箭引爆气球();
//        System.out.println(q.findMinArrowShots_optimize(new int[][]{{10, 16}, {2, 8}, {1, 6}, {7, 12}}));
//        System.out.println(q.findMinArrowShots_optimize(new int[][]{{1, 2}, {3, 4}, {5, 6}, {7, 8}}));
//        System.out.println(q.findMinArrowShots_optimize(new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 5}}));
        System.out.println(q.findMinArrowShots_optimize(new int[][]{{3, 9}, {7, 12}, {3, 8}, {6, 8}, {9, 10}, {2, 9}, {0, 9}, {3, 9}, {0, 6}, {2, 8}}));
    }
}