LeetCode.452.Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球

题目描述

56 Merge Intervals
https://leetcode-cn.com/problems/merge-intervals/

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

---

相似题目

LeetCode.836.Rectangle Overlap 矩形重叠
LeetCode.056.Merge Intervals 合并重叠区间
LeetCode.452.Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球

---

解题过程

想要用最少的箭穿过所有气球，肯定得每只箭射穿尽可能多的气球，这里的尽可能多就能把思路引到贪心算法上
所以我们应该把相邻的气球尽可能的聚集在一起，然后在重叠气球个数最多的重叠区域内射箭。
这里的 相邻的 就要求我们 先排序， 重叠最多 提示我们这是一个 贪心策略。
这种区间问题，一般都是贪心，做题多了看到就会想到用贪心，先排序

具体实现上：按区间的左端点升序排序，则排序后重叠区间肯定是相邻聚集在一起的。然后从前往后遍历区间，两两求交集，一直到相邻的不再相交则需要一直箭穿过。

时间复杂度 O(nlogn)，空间复杂度 O(n)

private static class SolutionV2020 {
    public int findMinArrowShots(int[][] points) {
        if (null == points || 0 == points.length) {
            return 0;
        }
        Arrays.sort(points, (point1, point2) -> point1[0] - point2[0]);
        int minArrows = 0;
        int[] current = points[0];
        for (int i = 1; i < points.length; i++) {
            if (isIntersect(current, points[i])) {
                current = intersect(current, points[i]);
            } else {
                minArrows++;
                current = points[i];
            }
        }
        // 特殊处理最后一个线段
        minArrows = isIntersect(current, points[points.length - 1]) ? minArrows + 1 : minArrows + 2;
        return minArrows;
    }

    // 判断线段 segment1 和 segment2 是否相交
    private boolean isIntersect(int[] segment1, int[] segment2) {
        return Math.max(segment1[0], segment2[0]) <= Math.min(segment1[1], segment2[1]);
    }

    // segment1 和 segment2 的交集(已知相交的前提下)
    private int[] intersect(int[] segment1, int[] segment2) {
        return new int[] {Math.max(segment1[0], segment2[0]), Math.min(segment1[1], segment2[1])};
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_452_MinimumNumberOfArrowsToBurstBalloons.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_452_MinimumNumberOfArrowsToBurstBalloons.java

---