本文主要是介绍leetcode 452. Minimum Number of Arrows to Burst Balloons | 452. 用最少数量的箭引爆气球（左程云：最大线段重合问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/
题解
重叠区间问题可以总结为在坐标轴上若干个位置为 (start(i),end(i)) 的区间，要求求解这些区间中有多少个不重叠区间，或者合并重叠的区间。
对于重叠区间问题，海外版评论区有人总结了模板，见 A Concise Template for “Overlapping Interval Problem”
该问题分两类：第一类求重叠区间个数（leetcode 452，435），第二类求合并后的区间（leetcode 56，763）。
对于第一类问题，通常按照end排序，维护一个end变量即可。
对于第二类问题，通常按照start排序，维护一个数组，每次取最后一个数作为比较的标准。
注意按照 start 或者 end 排序两种方式都可以求解，只是在不同情况下用其中之一代码编写更简洁。
本文总结了leetcode中重叠区间问题的题目，涉及到的题目如下：
- leetcode 56 合并区间
- leetcode 452 射气球
- leetcode 435 无重叠区间
- leetcode 763 划分字母区间
本题思路
回到本题，思路是，维护一个小根堆，里面存 end，当 start 大于最小的 end 时，说明前面的线段和当前的线段不可能同时被切，所以把前面的线段全部一刀切。
后来发现，不需要维护小根堆，只要用一个变量维护最小值就可以了。
class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (o1, o2) -> (long) o1[0] - (long) o2[0] > 0 ? 1 : -1);int count = 0;long minEnd = Long.MAX_VALUE;for (int[] pair : points) {if (minEnd != Long.MAX_VALUE && pair[0] > minEnd) {minEnd = Long.MAX_VALUE;count++;}minEnd = Math.min(minEnd, pair[1]);}return count + 1; // 清算结尾}
}
思路来源：左程云“最大线段重合问题”
另外，对于“求重叠最多的绳子条数”问题，见视频 15:49
package class04_07;import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;public class Code01_CoverMax {public static int maxCover1(int[][] lines) {int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int i = 0; i < lines.length; i++) {min = Math.min(min, lines[i][0]);max = Math.max(max, lines[i][1]);}int cover = 0;for (double p = min + 0.5; p < max; p += 1) {int cur = 0;for (int i = 0; i < lines.length; i++) {if (lines[i][0] < p && lines[i][1] > p) {cur++;}}cover = Math.max(cover, cur);}return cover;}public static int maxCover2(int[][] m) {Line[] lines = new Line[m.length];for (int i = 0; i < m.length; i++) {lines[i] = new Line(m[i][0], m[i][1]);}Arrays.sort(lines, new StartComparator());// 小根堆，每一条线段的结尾数值，使用默认的PriorityQueue<Integer> heap = new PriorityQueue<>();int max = 0;for (int i = 0; i < lines.length; i++) {// lines[i] -> cur 在黑盒中，把<=cur.start 东西都弹出while (!heap.isEmpty() && heap.peek() <= lines[i].start) {heap.poll();}heap.add(lines[i].end);max = Math.max(max, heap.size());}return max;}public static class Line {public int start;public int end;public Line(int s, int e) {start = s;end = e;}}public static class EndComparator implements Comparator<Line> {@Overridepublic int compare(Line o1, Line o2) {return o1.end - o2.end;}}// for testpublic static int[][] generateLines(int N, int L, int R) {int size = (int) (Math.random() * N) + 1;int[][] ans = new int[size][2];for (int i = 0; i < size; i++) {int a = L + (int) (Math.random() * (R - L + 1));int b = L + (int) (Math.random() * (R - L + 1));if (a == b) {b = a + 1;}ans[i][0] = Math.min(a, b);ans[i][1] = Math.max(a, b);}return ans;}public static class StartComparator implements Comparator<Line> {@Overridepublic int compare(Line o1, Line o2) {return o1.start - o2.start;}}public static void main(String[] args) {Line l1 = new Line(4, 9);Line l2 = new Line(1, 4);Line l3 = new Line(7, 15);Line l4 = new Line(2, 4);Line l5 = new Line(4, 6);Line l6 = new Line(3, 7);// 底层堆结构，heapPriorityQueue<Line> heap = new PriorityQueue<>(new StartComparator());heap.add(l1);heap.add(l2);heap.add(l3);heap.add(l4);heap.add(l5);heap.add(l6);while (!heap.isEmpty()) {Line cur = heap.poll();System.out.println(cur.start + "," + cur.end);}System.out.println("test begin");int N = 100;int L = 0;int R = 200;int testTimes = 200000;for (int i = 0; i < testTimes; i++) {int[][] lines = generateLines(N, L, R);int ans1 = maxCover1(lines);int ans2 = maxCover2(lines);if (ans1 != ans2) {System.out.println("Oops!");}}System.out.println("test end");}
}
这篇关于leetcode 452. Minimum Number of Arrows to Burst Balloons | 452. 用最少数量的箭引爆气球（左程云：最大线段重合问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
